

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





class A__    :



 """simple docstring"""







 def __init__(		self :	Any       ):






      '''simple docstring'''




      _lowerCAmelCase   :					Union[str, Any]        =    {}

 def    __magic_name__       (		self :	Any     ,						A_ :	Optional[Any]     ,						A_ :	Optional[int]     ,						A_ :	str=1       ):






      '''simple docstring'''




      if self.graph.get(__snake_case       ):
           if self.graph[u].count([w, v]       ) == 0:
                self.graph[u].append([w, v]       )
      else:
           _lowerCAmelCase   :					Dict        =    [[w, v]]
      if not self.graph.get(__snake_case       ):
           _lowerCAmelCase   :					List[Any]        =    []

 def    __magic_name__       (		self :	int       ):






      '''simple docstring'''




      return list(self.graph       )

 def    __magic_name__       (		self :	Union[str, Any]     ,						A_ :	List[Any]     ,						A_ :	Optional[Any]       ):






      '''simple docstring'''




      if self.graph.get(__snake_case       ):
           for _ in self.graph[u]:
                if _[1] == v:
                     self.graph[u].remove(__snake_case       )

 def    __magic_name__       (		self :	Optional[int]     ,						A_ :	Tuple=-2     ,						A_ :	int=-1       ):






      '''simple docstring'''




      if s == d:
           return []
      _lowerCAmelCase   :					int        =    []
      _lowerCAmelCase   :					Tuple        =    []
      if s == -2:
           _lowerCAmelCase   :					str        =    list(self.graph       )[0]
      stack.append(__snake_case       )
      visited.append(__snake_case       )
      _lowerCAmelCase   :					Dict        =    s

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

            # check if all the children are visited
           if s == ss:
                stack.pop()
                if len(__snake_case       ) != 0:
                     _lowerCAmelCase   :					List[str]        =    stack[len(__snake_case       ) - 1]
           else:
                _lowerCAmelCase   :					Optional[Any]        =    ss

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

 def    __magic_name__       (		self :	Union[str, Any]     ,						A_ :	List[Any]=-1       ):






      '''simple docstring'''




      if c == -1:
           _lowerCAmelCase   :					str        =    floor(random() * 1_0_0_0_0       ) + 1_0
      for i in range(__snake_case       ):
           # every vertex has max 100 edges
           for _ in range(floor(random() * 1_0_2       ) + 1       ):
                _lowerCAmelCase   :					Dict        =    floor(random() * c       ) + 1
                if n != i:
                     self.add_pair(__snake_case     ,						__snake_case     ,						1       )

 def    __magic_name__       (		self :	Optional[Any]     ,						A_ :	str=-2       ):






      '''simple docstring'''




      _lowerCAmelCase   :					List[str]        =    deque()
      _lowerCAmelCase   :					List[str]        =    []
      if s == -2:
           _lowerCAmelCase   :					Any        =    list(self.graph       )[0]
      d.append(__snake_case       )
      visited.append(__snake_case       )
      while d:
           _lowerCAmelCase   :					Optional[int]        =    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    __magic_name__       (		self :	str     ,						A_ :	str       ):






      '''simple docstring'''




      _lowerCAmelCase   :					Union[str, Any]        =    0
      for x in self.graph:
           for y in self.graph[x]:
                if y[1] == u:
                     count += 1
      return count

 def    __magic_name__       (		self :	int     ,						A_ :	List[str]       ):






      '''simple docstring'''




      return len(self.graph[u]       )

 def    __magic_name__       (		self :	str     ,						A_ :	List[Any]=-2       ):






      '''simple docstring'''




      _lowerCAmelCase   :					List[Any]        =    []
      _lowerCAmelCase   :					Dict        =    []
      if s == -2:
           _lowerCAmelCase   :					Union[str, Any]        =    list(self.graph       )[0]
      stack.append(__snake_case       )
      visited.append(__snake_case       )
      _lowerCAmelCase   :					Optional[int]        =    s
      _lowerCAmelCase   :					List[Any]        =    []

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

            # check if all the children are visited
           if s == ss:
                sorted_nodes.append(stack.pop()       )
                if len(__snake_case       ) != 0:
                     _lowerCAmelCase   :					Optional[int]        =    stack[len(__snake_case       ) - 1]
           else:
                _lowerCAmelCase   :					Union[str, Any]        =    ss

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

 def    __magic_name__       (		self :	int       ):






      '''simple docstring'''




      _lowerCAmelCase   :					Any        =    []
      _lowerCAmelCase   :					Optional[int]        =    []
      _lowerCAmelCase   :					Any        =    list(self.graph       )[0]
      stack.append(__snake_case       )
      visited.append(__snake_case       )
      _lowerCAmelCase   :					int        =    -2
      _lowerCAmelCase   :					Union[str, Any]        =    []
      _lowerCAmelCase   :					str        =    s
      _lowerCAmelCase   :					str        =    False
      _lowerCAmelCase   :					int        =    set()

      while True:
           # check if there is any non isolated nodes
           if len(self.graph[s]       ) != 0:
                _lowerCAmelCase   :					Dict        =    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
                     ):
                          _lowerCAmelCase   :					str        =    len(__snake_case       ) - 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]       )
                          _lowerCAmelCase   :					Union[str, Any]        =    node[1]
                          break

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

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

 def    __magic_name__       (		self :	Optional[Any]       ):






      '''simple docstring'''




      _lowerCAmelCase   :					Union[str, Any]        =    []
      _lowerCAmelCase   :					str        =    []
      _lowerCAmelCase   :					List[str]        =    list(self.graph       )[0]
      stack.append(__snake_case       )
      visited.append(__snake_case       )
      _lowerCAmelCase   :					List[str]        =    -2
      _lowerCAmelCase   :					Optional[Any]        =    []
      _lowerCAmelCase   :					Optional[Any]        =    s
      _lowerCAmelCase   :					Tuple        =    False
      _lowerCAmelCase   :					Optional[Any]        =    set()

      while True:
           # check if there is any non isolated nodes
           if len(self.graph[s]       ) != 0:
                _lowerCAmelCase   :					str        =    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
                     ):
                          _lowerCAmelCase   :					List[Any]        =    len(__snake_case       ) - 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]       )
                          _lowerCAmelCase   :					Tuple        =    node[1]
                          break

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

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

 def    __magic_name__       (		self :	List[Any]     ,						A_ :	List[str]=-2     ,						A_ :	Optional[Any]=-1       ):






      '''simple docstring'''




      _lowerCAmelCase   :					Union[str, Any]        =    time()
      self.dfs(__snake_case     ,						__snake_case       )
      _lowerCAmelCase   :					Optional[Any]        =    time()
      return end - begin


 def    __magic_name__       (		self :	int     ,						A_ :	int=-2       ):






      '''simple docstring'''




      _lowerCAmelCase   :					List[Any]        =    time()
      self.bfs(__snake_case       )
      _lowerCAmelCase   :					Tuple        =    time()
      return end - begin





class A__    :



 """simple docstring"""







 def __init__(		self :	Union[str, Any]       ):






      '''simple docstring'''




      _lowerCAmelCase   :					Any        =    {}

 def    __magic_name__       (		self :	Union[str, Any]     ,						A_ :	int     ,						A_ :	Dict     ,						A_ :	List[str]=1       ):






      '''simple docstring'''




      if self.graph.get(__snake_case       ):
           # 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
           _lowerCAmelCase   :					int        =    [[w, v]]
      # add the other way
      if self.graph.get(__snake_case       ):
           # 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
           _lowerCAmelCase   :					str        =    [[w, u]]

 def    __magic_name__       (		self :	Tuple     ,						A_ :	Optional[int]     ,						A_ :	Tuple       ):






      '''simple docstring'''




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

 def    __magic_name__       (		self :	int     ,						A_ :	int=-2     ,						A_ :	List[Any]=-1       ):






      '''simple docstring'''




      if s == d:
           return []
      _lowerCAmelCase   :					int        =    []
      _lowerCAmelCase   :					str        =    []
      if s == -2:
           _lowerCAmelCase   :					Dict        =    list(self.graph       )[0]
      stack.append(__snake_case       )
      visited.append(__snake_case       )
      _lowerCAmelCase   :					Optional[int]        =    s

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

            # check if all the children are visited
           if s == ss:
                stack.pop()
                if len(__snake_case       ) != 0:
                     _lowerCAmelCase   :					Optional[int]        =    stack[len(__snake_case       ) - 1]
           else:
                _lowerCAmelCase   :					Any        =    ss

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

 def    __magic_name__       (		self :	Dict     ,						A_ :	List[str]=-1       ):






      '''simple docstring'''




      if c == -1:
           _lowerCAmelCase   :					str        =    floor(random() * 1_0_0_0_0       ) + 1_0
      for i in range(__snake_case       ):
           # every vertex has max 100 edges
           for _ in range(floor(random() * 1_0_2       ) + 1       ):
                _lowerCAmelCase   :					Optional[int]        =    floor(random() * c       ) + 1
                if n != i:
                     self.add_pair(__snake_case     ,						__snake_case     ,						1       )

 def    __magic_name__       (		self :	int     ,						A_ :	str=-2       ):






      '''simple docstring'''




      _lowerCAmelCase   :					Optional[int]        =    deque()
      _lowerCAmelCase   :					List[Any]        =    []
      if s == -2:
           _lowerCAmelCase   :					Union[str, Any]        =    list(self.graph       )[0]
      d.append(__snake_case       )
      visited.append(__snake_case       )
      while d:
           _lowerCAmelCase   :					str        =    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    __magic_name__       (		self :	int     ,						A_ :	Any       ):






      '''simple docstring'''




      return len(self.graph[u]       )

 def    __magic_name__       (		self :	Tuple       ):






      '''simple docstring'''




      _lowerCAmelCase   :					Optional[int]        =    []
      _lowerCAmelCase   :					Optional[Any]        =    []
      _lowerCAmelCase   :					Any        =    list(self.graph       )[0]
      stack.append(__snake_case       )
      visited.append(__snake_case       )
      _lowerCAmelCase   :					Optional[Any]        =    -2
      _lowerCAmelCase   :					Optional[int]        =    []
      _lowerCAmelCase   :					int        =    s
      _lowerCAmelCase   :					str        =    False
      _lowerCAmelCase   :					List[Any]        =    set()

      while True:
           # check if there is any non isolated nodes
           if len(self.graph[s]       ) != 0:
                _lowerCAmelCase   :					List[Any]        =    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
                     ):
                          _lowerCAmelCase   :					Tuple        =    len(__snake_case       ) - 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]       )
                          _lowerCAmelCase   :					Any        =    node[1]
                          break

            # check if all the children are visited
           if s == ss:
                stack.pop()
                _lowerCAmelCase   :					str        =    True
                if len(__snake_case       ) != 0:
                     _lowerCAmelCase   :					Dict        =    stack[len(__snake_case       ) - 1]
           else:
                _lowerCAmelCase   :					Tuple        =    False
                indirect_parents.append(__snake_case       )
                _lowerCAmelCase   :					Union[str, Any]        =    s
                _lowerCAmelCase   :					Any        =    ss

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

 def    __magic_name__       (		self :	Any       ):






      '''simple docstring'''




      _lowerCAmelCase   :					Optional[Any]        =    []
      _lowerCAmelCase   :					Union[str, Any]        =    []
      _lowerCAmelCase   :					Any        =    list(self.graph       )[0]
      stack.append(__snake_case       )
      visited.append(__snake_case       )
      _lowerCAmelCase   :					Any        =    -2
      _lowerCAmelCase   :					Dict        =    []
      _lowerCAmelCase   :					Dict        =    s
      _lowerCAmelCase   :					Union[str, Any]        =    False
      _lowerCAmelCase   :					List[Any]        =    set()

      while True:
           # check if there is any non isolated nodes
           if len(self.graph[s]       ) != 0:
                _lowerCAmelCase   :					Union[str, Any]        =    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
                     ):
                          _lowerCAmelCase   :					int        =    len(__snake_case       ) - 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]       )
                          _lowerCAmelCase   :					Dict        =    node[1]
                          break

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

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

 def    __magic_name__       (		self :	List[Any]       ):






      '''simple docstring'''




      return list(self.graph       )

 def    __magic_name__       (		self :	Optional[int]     ,						A_ :	Dict=-2     ,						A_ :	int=-1       ):






      '''simple docstring'''




      _lowerCAmelCase   :					str        =    time()
      self.dfs(__snake_case     ,						__snake_case       )
      _lowerCAmelCase   :					Tuple        =    time()
      return end - begin


 def    __magic_name__       (		self :	List[str]     ,						A_ :	Union[str, Any]=-2       ):






      '''simple docstring'''




      _lowerCAmelCase   :					List[Any]        =    time()
      self.bfs(__snake_case       )
      _lowerCAmelCase   :					Tuple        =    time()
      return end - begin









from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_tensorflow_text_available, is_torch_available


__UpperCAmelCase    				=     {
    'configuration_ernie': ['ERNIE_PRETRAINED_CONFIG_ARCHIVE_MAP', 'ErnieConfig', 'ErnieOnnxConfig'],
}

try:
  if not is_torch_available():
    raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
  pass
else:
  __UpperCAmelCase    				=     [
      'ERNIE_PRETRAINED_MODEL_ARCHIVE_LIST',
      'ErnieForCausalLM',
      'ErnieForMaskedLM',
      'ErnieForMultipleChoice',
      'ErnieForNextSentencePrediction',
      'ErnieForPreTraining',
      'ErnieForQuestionAnswering',
      'ErnieForSequenceClassification',
      'ErnieForTokenClassification',
      'ErnieModel',
      'ErniePreTrainedModel',
  ]

if TYPE_CHECKING:
  from .configuration_ernie import ERNIE_PRETRAINED_CONFIG_ARCHIVE_MAP, ErnieConfig, ErnieOnnxConfig

  try:
    if not is_torch_available():
      raise OptionalDependencyNotAvailable()
  except OptionalDependencyNotAvailable:
    pass
  else:
    from .modeling_ernie import (
        ERNIE_PRETRAINED_MODEL_ARCHIVE_LIST,
        ErnieForCausalLM,
        ErnieForMaskedLM,
        ErnieForMultipleChoice,
        ErnieForNextSentencePrediction,
        ErnieForPreTraining,
        ErnieForQuestionAnswering,
        ErnieForSequenceClassification,
        ErnieForTokenClassification,
        ErnieModel,
        ErniePreTrainedModel,
    )

else:
  import sys

  __UpperCAmelCase    				=     _LazyModule(__name__, globals()['__file__'], _import_structure, module_spec=__spec__)






