





"""simple docstring"""






import tensorflow as tf

from ...tf_utils import shape_list



class 	lowerCAmelCase					(      tf.keras.layers.Layer							):






       def __init__(   self    ,  a__    ,  a__    ,  a__    ,  a__    ,  a__=1    ,  a__=False    ,  **a__     ):
              super().__init__(**a__     )

              _UpperCAmelCase     =     vocab_size
              _UpperCAmelCase     =     d_embed
              _UpperCAmelCase     =     d_proj

              _UpperCAmelCase     =     cutoffs + [vocab_size]
              _UpperCAmelCase     =     [0] + self.cutoffs
              _UpperCAmelCase     =     div_val

              _UpperCAmelCase     =     self.cutoffs[0]
              _UpperCAmelCase     =     len(self.cutoffs     ) - 1
              _UpperCAmelCase     =     self.shortlist_size + self.n_clusters
              _UpperCAmelCase     =     keep_order

              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []






       def 							__A (   self    ,  a__     ):
              if self.n_clusters > 0:
                     _UpperCAmelCase     =     self.add_weight(
                         shape=(self.n_clusters, self.d_embed)    ,  initializer='zeros'    ,  trainable=a__    ,  name='cluster_weight'     )
                     _UpperCAmelCase     =     self.add_weight(
                         shape=(self.n_clusters,)    ,  initializer='zeros'    ,  trainable=a__    ,  name='cluster_bias'     )

              if self.div_val == 1:
                     for i in range(len(self.cutoffs     )     ):
                            if self.d_proj != self.d_embed:
                                   _UpperCAmelCase     =     self.add_weight(
                                       shape=(self.d_embed, self.d_proj)    ,  initializer='zeros'    ,  trainable=a__    ,  name=f"""out_projs_._{i}"""    ,  )
                                   self.out_projs.append(a__     )
                            else:
                                   self.out_projs.append(a__     )
                            _UpperCAmelCase     =     self.add_weight(
                                shape=(self.vocab_size, self.d_embed)    ,  initializer='zeros'    ,  trainable=a__    ,  name=f"""out_layers_._{i}_._weight"""    ,  )
                            _UpperCAmelCase     =     self.add_weight(
                                shape=(self.vocab_size,)    ,  initializer='zeros'    ,  trainable=a__    ,  name=f"""out_layers_._{i}_._bias"""    ,  )
                            self.out_layers.append((weight, bias)     )
              else:
                     for i in range(len(self.cutoffs     )     ):
                            _UpperCAmelCase    ,							_UpperCAmelCase     =     self.cutoff_ends[i], self.cutoff_ends[i + 1]
                            _UpperCAmelCase     =     self.d_embed // (self.div_val**i)

                            _UpperCAmelCase     =     self.add_weight(
                                shape=(d_emb_i, self.d_proj)    ,  initializer='zeros'    ,  trainable=a__    ,  name=f"""out_projs_._{i}"""     )
                            self.out_projs.append(a__     )
                            _UpperCAmelCase     =     self.add_weight(
                                shape=(r_idx - l_idx, d_emb_i)    ,  initializer='zeros'    ,  trainable=a__    ,  name=f"""out_layers_._{i}_._weight"""    ,  )
                            _UpperCAmelCase     =     self.add_weight(
                                shape=(r_idx - l_idx,)    ,  initializer='zeros'    ,  trainable=a__    ,  name=f"""out_layers_._{i}_._bias"""    ,  )
                            self.out_layers.append((weight, bias)     )
              super().build(a__     )






       @staticmethod
       def 							__A (   a__    ,  a__    ,  a__    ,  a__=None     ):
              _UpperCAmelCase     =     x
              if proj is not None:
                     _UpperCAmelCase     =     tf.einsum('ibd,ed->ibe'    ,  a__    ,  a__     )
              return tf.einsum('ibd,nd->ibn'    ,  a__    ,  a__     ) + b






       @staticmethod
       def 							__A (   a__    ,  a__     ):
              _UpperCAmelCase     =     shape_list(a__     )
              _UpperCAmelCase     =     tf.range(lp_size[0]    ,  dtype=target.dtype     )
              _UpperCAmelCase     =     tf.stack([r, target]    ,  1     )
              return tf.gather_nd(a__    ,  a__     )






       def 							__A (   self    ,  a__    ,  a__    ,  a__=True    ,  a__=False     ):
              _UpperCAmelCase     =     0
              if self.n_clusters == 0:
                     _UpperCAmelCase     =     self._logit(a__    ,  self.out_layers[0][0]    ,  self.out_layers[0][1]    ,  self.out_projs[0]     )
                     if target is not None:
                            _UpperCAmelCase     =     tf.nn.sparse_softmax_cross_entropy_with_logits(labels=a__    ,  logits=a__     )
                     _UpperCAmelCase     =     tf.nn.log_softmax(a__    ,  axis=-1     )
              else:
                     _UpperCAmelCase     =     shape_list(a__     )
                     _UpperCAmelCase     =     []
                     _UpperCAmelCase     =     tf.zeros(hidden_sizes[:2]     )
                     for i in range(len(self.cutoffs     )     ):
                            _UpperCAmelCase    ,							_UpperCAmelCase     =     self.cutoff_ends[i], self.cutoff_ends[i + 1]
                            if target is not None:
                                   _UpperCAmelCase     =     (target >= l_idx) & (target < r_idx)
                                   _UpperCAmelCase     =     tf.where(a__     )
                                   _UpperCAmelCase     =     tf.boolean_mask(a__    ,  a__     ) - l_idx

                            if self.div_val == 1:
                                   _UpperCAmelCase     =     self.out_layers[0][0][l_idx:r_idx]
                                   _UpperCAmelCase     =     self.out_layers[0][1][l_idx:r_idx]
                            else:
                                   _UpperCAmelCase     =     self.out_layers[i][0]
                                   _UpperCAmelCase     =     self.out_layers[i][1]

                            if i == 0:
                                   _UpperCAmelCase     =     tf.concat([cur_W, self.cluster_weight]    ,  0     )
                                   _UpperCAmelCase     =     tf.concat([cur_b, self.cluster_bias]    ,  0     )

                                   _UpperCAmelCase     =     self._logit(a__    ,  a__    ,  a__    ,  self.out_projs[0]     )
                                   _UpperCAmelCase     =     tf.nn.log_softmax(a__     )
                                   out.append(head_logprob[..., : self.cutoffs[0]]     )
                                   if target is not None:
                                          _UpperCAmelCase     =     tf.boolean_mask(a__    ,  a__     )
                                          _UpperCAmelCase     =     self._gather_logprob(a__    ,  a__     )
                            else:
                                   _UpperCAmelCase     =     self._logit(a__    ,  a__    ,  a__    ,  self.out_projs[i]     )
                                   _UpperCAmelCase     =     tf.nn.log_softmax(a__     )
                                   _UpperCAmelCase     =     self.cutoffs[0] + i - 1  # No probability for the head cluster
                                   _UpperCAmelCase     =     head_logprob[..., cluster_prob_idx, None] + tail_logprob
                                   out.append(a__     )
                                   if target is not None:
                                          _UpperCAmelCase     =     tf.boolean_mask(a__    ,  a__     )
                                          _UpperCAmelCase     =     tf.boolean_mask(a__    ,  a__     )
                                          _UpperCAmelCase     =     self._gather_logprob(a__    ,  a__     )
                                          cur_logprob += cur_head_logprob[:, self.cutoff_ends[1] + i - 1]
                            if target is not None:
                                   loss += tf.scatter_nd(a__    ,  -cur_logprob    ,  shape_list(a__     )     )
                     _UpperCAmelCase     =     tf.concat(a__    ,  axis=-1     )

              if target is not None:
                     if return_mean:
                            _UpperCAmelCase     =     tf.reduce_mean(a__     )
                     # Add the training-time loss value to the layer using `self.add_loss()`.
                     self.add_loss(a__     )

                     # Log the loss as a metric (we could log arbitrary metrics,
                     # including different metrics for training and inference.
                     self.add_metric(a__    ,  name=self.name    ,  aggregation='mean' if return_mean else ''     )

              return out













"""simple docstring"""






from collections import deque
from math import floor
from random import random
from time import time



class 	lowerCAmelCase					:






       def __init__(   self     ):
              _UpperCAmelCase     =     {}






       def 							__A (   self    ,  a__    ,  a__    ,  a__=1     ):
              if self.graph.get(a__     ):
                     if self.graph[u].count([w, v]     ) == 0:
                            self.graph[u].append([w, v]     )
              else:
                     _UpperCAmelCase     =     [[w, v]]
              if not self.graph.get(a__     ):
                     _UpperCAmelCase     =     []






       def 							__A (   self     ):
              return list(self.graph     )






       def 							__A (   self    ,  a__    ,  a__     ):
              if self.graph.get(a__     ):
                     for _ in self.graph[u]:
                            if _[1] == v:
                                   self.graph[u].remove(a__     )






       def 							__A (   self    ,  a__=-2    ,  a__=-1     ):
              if s == d:
                     return []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              if s == -2:
                     _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     s

              while True:
                     # check if there is any non isolated nodes
                     if len(self.graph[s]     ) != 0:
                            _UpperCAmelCase     =     s
                            for node in self.graph[s]:
                                   if visited.count(node[1]     ) < 1:
                                          if node[1] == d:
                                                 visited.append(a__     )
                                                 return visited
                                          else:
                                                 stack.append(node[1]     )
                                                 visited.append(node[1]     )
                                                 _UpperCAmelCase     =     node[1]
                                                 break

            # check if all the children are visited
                     if s == ss:
                            stack.pop()
                            if len(a__     ) != 0:
                                   _UpperCAmelCase     =     stack[len(a__     ) - 1]
                     else:
                            _UpperCAmelCase     =     ss

                     # check if se have reached the starting point
                     if len(a__     ) == 0:
                            return visited






       def 							__A (   self    ,  a__=-1     ):
              if c == -1:
                     _UpperCAmelCase     =     floor(random() * 1_00_00     ) + 10
              for i in range(a__     ):
                     # every vertex has max 100 edges
                     for _ in range(floor(random() * 1_02     ) + 1     ):
                            _UpperCAmelCase     =     floor(random() * c     ) + 1
                            if n != i:
                                   self.add_pair(a__    ,  a__    ,  1     )






       def 							__A (   self    ,  a__=-2     ):
              _UpperCAmelCase     =     deque()
              _UpperCAmelCase     =     []
              if s == -2:
                     _UpperCAmelCase     =     list(self.graph     )[0]
              d.append(a__     )
              visited.append(a__     )
              while d:
                     _UpperCAmelCase     =     d.popleft()
                     if len(self.graph[s]     ) != 0:
                            for node in self.graph[s]:
                                   if visited.count(node[1]     ) < 1:
                                          d.append(node[1]     )
                                          visited.append(node[1]     )
              return visited






       def 							__A (   self    ,  a__     ):
              _UpperCAmelCase     =     0
              for x in self.graph:
                     for y in self.graph[x]:
                            if y[1] == u:
                                   count += 1
              return count






       def 							__A (   self    ,  a__     ):
              return len(self.graph[u]     )






       def 							__A (   self    ,  a__=-2     ):
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              if s == -2:
                     _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     s
              _UpperCAmelCase     =     []

              while True:
                     # check if there is any non isolated nodes
                     if len(self.graph[s]     ) != 0:
                            _UpperCAmelCase     =     s
                            for node in self.graph[s]:
                                   if visited.count(node[1]     ) < 1:
                                          stack.append(node[1]     )
                                          visited.append(node[1]     )
                                          _UpperCAmelCase     =     node[1]
                                          break

            # check if all the children are visited
                     if s == ss:
                            sorted_nodes.append(stack.pop()     )
                            if len(a__     ) != 0:
                                   _UpperCAmelCase     =     stack[len(a__     ) - 1]
                     else:
                            _UpperCAmelCase     =     ss

                     # check if se have reached the starting point
                     if len(a__     ) == 0:
                            return sorted_nodes






       def 							__A (   self     ):
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     -2
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     s
              _UpperCAmelCase     =     False
              _UpperCAmelCase     =     set()

              while True:
                     # check if there is any non isolated nodes
                     if len(self.graph[s]     ) != 0:
                            _UpperCAmelCase     =     s
                            for node in self.graph[s]:
                                   if (
                                       visited.count(node[1]     ) > 0
                                       and node[1] != parent
                                       and indirect_parents.count(node[1]     ) > 0
                                       and not on_the_way_back
                                   ):
                                          _UpperCAmelCase     =     len(a__     ) - 1
                                          while len_stack >= 0:
                                                 if stack[len_stack] == node[1]:
                                                        anticipating_nodes.add(node[1]     )
                                                        break
                                                 else:
                                                        anticipating_nodes.add(stack[len_stack]     )
                                                        len_stack -= 1
                                   if visited.count(node[1]     ) < 1:
                                          stack.append(node[1]     )
                                          visited.append(node[1]     )
                                          _UpperCAmelCase     =     node[1]
                                          break

            # check if all the children are visited
                     if s == ss:
                            stack.pop()
                            _UpperCAmelCase     =     True
                            if len(a__     ) != 0:
                                   _UpperCAmelCase     =     stack[len(a__     ) - 1]
                     else:
                            _UpperCAmelCase     =     False
                            indirect_parents.append(a__     )
                            _UpperCAmelCase     =     s
                            _UpperCAmelCase     =     ss

                     # check if se have reached the starting point
                     if len(a__     ) == 0:
                            return list(a__     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     -2
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     s
              _UpperCAmelCase     =     False
              _UpperCAmelCase     =     set()

              while True:
                     # check if there is any non isolated nodes
                     if len(self.graph[s]     ) != 0:
                            _UpperCAmelCase     =     s
                            for node in self.graph[s]:
                                   if (
                                       visited.count(node[1]     ) > 0
                                       and node[1] != parent
                                       and indirect_parents.count(node[1]     ) > 0
                                       and not on_the_way_back
                                   ):
                                          _UpperCAmelCase     =     len(a__     ) - 1
                                          while len_stack_minus_one >= 0:
                                                 if stack[len_stack_minus_one] == node[1]:
                                                        anticipating_nodes.add(node[1]     )
                                                        break
                                                 else:
                                                        return True
                                   if visited.count(node[1]     ) < 1:
                                          stack.append(node[1]     )
                                          visited.append(node[1]     )
                                          _UpperCAmelCase     =     node[1]
                                          break

            # check if all the children are visited
                     if s == ss:
                            stack.pop()
                            _UpperCAmelCase     =     True
                            if len(a__     ) != 0:
                                   _UpperCAmelCase     =     stack[len(a__     ) - 1]
                     else:
                            _UpperCAmelCase     =     False
                            indirect_parents.append(a__     )
                            _UpperCAmelCase     =     s
                            _UpperCAmelCase     =     ss

                     # check if se have reached the starting point
                     if len(a__     ) == 0:
                            return False






       def 							__A (   self    ,  a__=-2    ,  a__=-1     ):
              _UpperCAmelCase     =     time()
              self.dfs(a__    ,  a__     )
              _UpperCAmelCase     =     time()
              return end - begin






       def 							__A (   self    ,  a__=-2     ):
              _UpperCAmelCase     =     time()
              self.bfs(a__     )
              _UpperCAmelCase     =     time()
              return end - begin



class 	lowerCAmelCase					:






       def __init__(   self     ):
              _UpperCAmelCase     =     {}






       def 							__A (   self    ,  a__    ,  a__    ,  a__=1     ):
              # check if the u exists
              if self.graph.get(a__     ):
                     # if there already is a edge
                     if self.graph[u].count([w, v]     ) == 0:
                            self.graph[u].append([w, v]     )
              else:
                     # if u does not exist
                     _UpperCAmelCase     =     [[w, v]]
              # add the other way
              if self.graph.get(a__     ):
                     # if there already is a edge
                     if self.graph[v].count([w, u]     ) == 0:
                            self.graph[v].append([w, u]     )
              else:
                     # if u does not exist
                     _UpperCAmelCase     =     [[w, u]]






       def 							__A (   self    ,  a__    ,  a__     ):
              if self.graph.get(a__     ):
                     for _ in self.graph[u]:
                            if _[1] == v:
                                   self.graph[u].remove(a__     )
        # the other way round
              if self.graph.get(a__     ):
                     for _ in self.graph[v]:
                            if _[1] == u:
                                   self.graph[v].remove(a__     )






       def 							__A (   self    ,  a__=-2    ,  a__=-1     ):
              if s == d:
                     return []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              if s == -2:
                     _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     s

              while True:
                     # check if there is any non isolated nodes
                     if len(self.graph[s]     ) != 0:
                            _UpperCAmelCase     =     s
                            for node in self.graph[s]:
                                   if visited.count(node[1]     ) < 1:
                                          if node[1] == d:
                                                 visited.append(a__     )
                                                 return visited
                                          else:
                                                 stack.append(node[1]     )
                                                 visited.append(node[1]     )
                                                 _UpperCAmelCase     =     node[1]
                                                 break

            # check if all the children are visited
                     if s == ss:
                            stack.pop()
                            if len(a__     ) != 0:
                                   _UpperCAmelCase     =     stack[len(a__     ) - 1]
                     else:
                            _UpperCAmelCase     =     ss

                     # check if se have reached the starting point
                     if len(a__     ) == 0:
                            return visited






       def 							__A (   self    ,  a__=-1     ):
              if c == -1:
                     _UpperCAmelCase     =     floor(random() * 1_00_00     ) + 10
              for i in range(a__     ):
                     # every vertex has max 100 edges
                     for _ in range(floor(random() * 1_02     ) + 1     ):
                            _UpperCAmelCase     =     floor(random() * c     ) + 1
                            if n != i:
                                   self.add_pair(a__    ,  a__    ,  1     )






       def 							__A (   self    ,  a__=-2     ):
              _UpperCAmelCase     =     deque()
              _UpperCAmelCase     =     []
              if s == -2:
                     _UpperCAmelCase     =     list(self.graph     )[0]
              d.append(a__     )
              visited.append(a__     )
              while d:
                     _UpperCAmelCase     =     d.popleft()
                     if len(self.graph[s]     ) != 0:
                            for node in self.graph[s]:
                                   if visited.count(node[1]     ) < 1:
                                          d.append(node[1]     )
                                          visited.append(node[1]     )
              return visited






       def 							__A (   self    ,  a__     ):
              return len(self.graph[u]     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     -2
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     s
              _UpperCAmelCase     =     False
              _UpperCAmelCase     =     set()

              while True:
                     # check if there is any non isolated nodes
                     if len(self.graph[s]     ) != 0:
                            _UpperCAmelCase     =     s
                            for node in self.graph[s]:
                                   if (
                                       visited.count(node[1]     ) > 0
                                       and node[1] != parent
                                       and indirect_parents.count(node[1]     ) > 0
                                       and not on_the_way_back
                                   ):
                                          _UpperCAmelCase     =     len(a__     ) - 1
                                          while len_stack >= 0:
                                                 if stack[len_stack] == node[1]:
                                                        anticipating_nodes.add(node[1]     )
                                                        break
                                                 else:
                                                        anticipating_nodes.add(stack[len_stack]     )
                                                        len_stack -= 1
                                   if visited.count(node[1]     ) < 1:
                                          stack.append(node[1]     )
                                          visited.append(node[1]     )
                                          _UpperCAmelCase     =     node[1]
                                          break

            # check if all the children are visited
                     if s == ss:
                            stack.pop()
                            _UpperCAmelCase     =     True
                            if len(a__     ) != 0:
                                   _UpperCAmelCase     =     stack[len(a__     ) - 1]
                     else:
                            _UpperCAmelCase     =     False
                            indirect_parents.append(a__     )
                            _UpperCAmelCase     =     s
                            _UpperCAmelCase     =     ss

                     # check if se have reached the starting point
                     if len(a__     ) == 0:
                            return list(a__     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     -2
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     s
              _UpperCAmelCase     =     False
              _UpperCAmelCase     =     set()

              while True:
                     # check if there is any non isolated nodes
                     if len(self.graph[s]     ) != 0:
                            _UpperCAmelCase     =     s
                            for node in self.graph[s]:
                                   if (
                                       visited.count(node[1]     ) > 0
                                       and node[1] != parent
                                       and indirect_parents.count(node[1]     ) > 0
                                       and not on_the_way_back
                                   ):
                                          _UpperCAmelCase     =     len(a__     ) - 1
                                          while len_stack_minus_one >= 0:
                                                 if stack[len_stack_minus_one] == node[1]:
                                                        anticipating_nodes.add(node[1]     )
                                                        break
                                                 else:
                                                        return True
                                   if visited.count(node[1]     ) < 1:
                                          stack.append(node[1]     )
                                          visited.append(node[1]     )
                                          _UpperCAmelCase     =     node[1]
                                          break

            # check if all the children are visited
                     if s == ss:
                            stack.pop()
                            _UpperCAmelCase     =     True
                            if len(a__     ) != 0:
                                   _UpperCAmelCase     =     stack[len(a__     ) - 1]
                     else:
                            _UpperCAmelCase     =     False
                            indirect_parents.append(a__     )
                            _UpperCAmelCase     =     s
                            _UpperCAmelCase     =     ss

                     # check if se have reached the starting point
                     if len(a__     ) == 0:
                            return False






       def 							__A (   self     ):
              return list(self.graph     )






       def 							__A (   self    ,  a__=-2    ,  a__=-1     ):
              _UpperCAmelCase     =     time()
              self.dfs(a__    ,  a__     )
              _UpperCAmelCase     =     time()
              return end - begin






       def 							__A (   self    ,  a__=-2     ):
              _UpperCAmelCase     =     time()
              self.bfs(a__     )
              _UpperCAmelCase     =     time()
              return end - begin






