


'''simple docstring'''



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



class      a    :


     """simple docstring"""






     def __init__(    self					:		Optional[int]      )						->							Any:
          __UpperCAmelCase     :			Union[str, Any]  							=      {}

     def 			lowerCamelCase__			(    self					:		Any							,			snake_case					:		List[Any]							,			snake_case					:		Union[str, Any]							,			snake_case					:		int=1      )						->							Dict:
          if self.graph.get(snake_case      ):
               if self.graph[u].count([w, v]      ) == 0:
                    self.graph[u].append([w, v]      )
          else:
               __UpperCAmelCase     :			Union[str, Any]  							=      [[w, v]]
          if not self.graph.get(snake_case      ):
               __UpperCAmelCase     :			str  							=      []

     def 			lowerCamelCase__			(    self					:		Union[str, Any]      )						->							List[str]:
          return list(self.graph      )

     def 			lowerCamelCase__			(    self					:		int							,			snake_case					:		Dict							,			snake_case					:		Optional[int]      )						->							Any:
          if self.graph.get(snake_case      ):
               for _ in self.graph[u]:
                    if _[1] == v:
                         self.graph[u].remove(snake_case      )

     def 			lowerCamelCase__			(    self					:		Optional[int]							,			snake_case					:		Optional[Any]=-2							,			snake_case					:		List[Any]=-1      )						->							List[Any]:
          if s == d:
               return []
          __UpperCAmelCase     :			Union[str, Any]  							=      []
          __UpperCAmelCase     :			Optional[int]  							=      []
          if s == -2:
               __UpperCAmelCase     :			int  							=      list(self.graph      )[0]
          stack.append(snake_case      )
          visited.append(snake_case      )
          __UpperCAmelCase     :			int  							=      s

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

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

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

     def 			lowerCamelCase__			(    self					:		str							,			snake_case					:		List[str]=-1      )						->							Optional[Any]:
          if c == -1:
               __UpperCAmelCase     :			Tuple  							=      floor(random() * 1_0000      ) + 10
          for i in range(snake_case      ):
               # every vertex has max 100 edges
               for _ in range(floor(random() * 102      ) + 1      ):
                    __UpperCAmelCase     :			Union[str, Any]  							=      floor(random() * c      ) + 1
                    if n != i:
                         self.add_pair(snake_case							,			snake_case							,			1      )

     def 			lowerCamelCase__			(    self					:		Optional[Any]							,			snake_case					:		Dict=-2      )						->							int:
          __UpperCAmelCase     :			Dict  							=      deque()
          __UpperCAmelCase     :			Tuple  							=      []
          if s == -2:
               __UpperCAmelCase     :			Any  							=      list(self.graph      )[0]
          d.append(snake_case      )
          visited.append(snake_case      )
          while d:
               __UpperCAmelCase     :			Optional[Any]  							=      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 			lowerCamelCase__			(    self					:		int							,			snake_case					:		Dict      )						->							List[str]:
          __UpperCAmelCase     :			Any  							=      0
          for x in self.graph:
               for y in self.graph[x]:
                    if y[1] == u:
                         count += 1
          return count

     def 			lowerCamelCase__			(    self					:		int							,			snake_case					:		Any      )						->							Optional[Any]:
          return len(self.graph[u]      )

     def 			lowerCamelCase__			(    self					:		Optional[Any]							,			snake_case					:		List[Any]=-2      )						->							Union[str, Any]:
          __UpperCAmelCase     :			Union[str, Any]  							=      []
          __UpperCAmelCase     :			List[Any]  							=      []
          if s == -2:
               __UpperCAmelCase     :			Optional[int]  							=      list(self.graph      )[0]
          stack.append(snake_case      )
          visited.append(snake_case      )
          __UpperCAmelCase     :			Dict  							=      s
          __UpperCAmelCase     :			Any  							=      []

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

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

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

     def 			lowerCamelCase__			(    self					:		Tuple      )						->							Tuple:
          __UpperCAmelCase     :			int  							=      []
          __UpperCAmelCase     :			List[Any]  							=      []
          __UpperCAmelCase     :			List[str]  							=      list(self.graph      )[0]
          stack.append(snake_case      )
          visited.append(snake_case      )
          __UpperCAmelCase     :			Union[str, Any]  							=      -2
          __UpperCAmelCase     :			str  							=      []
          __UpperCAmelCase     :			List[Any]  							=      s
          __UpperCAmelCase     :			Union[str, Any]  							=      False
          __UpperCAmelCase     :			Tuple  							=      set()

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

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

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

     def 			lowerCamelCase__			(    self					:		int      )						->							Union[str, Any]:
          __UpperCAmelCase     :			Any  							=      []
          __UpperCAmelCase     :			Dict  							=      []
          __UpperCAmelCase     :			Dict  							=      list(self.graph      )[0]
          stack.append(snake_case      )
          visited.append(snake_case      )
          __UpperCAmelCase     :			Tuple  							=      -2
          __UpperCAmelCase     :			Any  							=      []
          __UpperCAmelCase     :			List[str]  							=      s
          __UpperCAmelCase     :			Tuple  							=      False
          __UpperCAmelCase     :			Optional[Any]  							=      set()

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

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

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

     def 			lowerCamelCase__			(    self					:		str							,			snake_case					:		Any=-2							,			snake_case					:		List[str]=-1      )						->							int:
          __UpperCAmelCase     :			Dict  							=      time()
          self.dfs(snake_case							,			snake_case      )
          __UpperCAmelCase     :			Dict  							=      time()
          return end - begin






     def 			lowerCamelCase__			(    self					:		List[Any]							,			snake_case					:		Tuple=-2      )						->							Optional[int]:
          __UpperCAmelCase     :			Optional[int]  							=      time()
          self.bfs(snake_case      )
          __UpperCAmelCase     :			Optional[Any]  							=      time()
          return end - begin



class      a    :


     """simple docstring"""






     def __init__(    self					:		Tuple      )						->							Union[str, Any]:
          __UpperCAmelCase     :			Union[str, Any]  							=      {}

     def 			lowerCamelCase__			(    self					:		int							,			snake_case					:		Optional[Any]							,			snake_case					:		Optional[int]							,			snake_case					:		int=1      )						->							Tuple:
          # check if the u exists
          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
               __UpperCAmelCase     :			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
               __UpperCAmelCase     :			Tuple  							=      [[w, u]]

     def 			lowerCamelCase__			(    self					:		Optional[int]							,			snake_case					:		int							,			snake_case					:		Union[str, Any]      )						->							List[str]:
          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 			lowerCamelCase__			(    self					:		Tuple							,			snake_case					:		str=-2							,			snake_case					:		Optional[int]=-1      )						->							Dict:
          if s == d:
               return []
          __UpperCAmelCase     :			List[Any]  							=      []
          __UpperCAmelCase     :			Dict  							=      []
          if s == -2:
               __UpperCAmelCase     :			int  							=      list(self.graph      )[0]
          stack.append(snake_case      )
          visited.append(snake_case      )
          __UpperCAmelCase     :			List[Any]  							=      s

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

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

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

     def 			lowerCamelCase__			(    self					:		Dict							,			snake_case					:		Union[str, Any]=-1      )						->							List[str]:
          if c == -1:
               __UpperCAmelCase     :			Tuple  							=      floor(random() * 1_0000      ) + 10
          for i in range(snake_case      ):
               # every vertex has max 100 edges
               for _ in range(floor(random() * 102      ) + 1      ):
                    __UpperCAmelCase     :			List[str]  							=      floor(random() * c      ) + 1
                    if n != i:
                         self.add_pair(snake_case							,			snake_case							,			1      )

     def 			lowerCamelCase__			(    self					:		Dict							,			snake_case					:		str=-2      )						->							List[str]:
          __UpperCAmelCase     :			Dict  							=      deque()
          __UpperCAmelCase     :			Optional[int]  							=      []
          if s == -2:
               __UpperCAmelCase     :			int  							=      list(self.graph      )[0]
          d.append(snake_case      )
          visited.append(snake_case      )
          while d:
               __UpperCAmelCase     :			Dict  							=      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 			lowerCamelCase__			(    self					:		Union[str, Any]							,			snake_case					:		Optional[int]      )						->							int:
          return len(self.graph[u]      )

     def 			lowerCamelCase__			(    self					:		Optional[int]      )						->							int:
          __UpperCAmelCase     :			Tuple  							=      []
          __UpperCAmelCase     :			Tuple  							=      []
          __UpperCAmelCase     :			Tuple  							=      list(self.graph      )[0]
          stack.append(snake_case      )
          visited.append(snake_case      )
          __UpperCAmelCase     :			Optional[Any]  							=      -2
          __UpperCAmelCase     :			int  							=      []
          __UpperCAmelCase     :			int  							=      s
          __UpperCAmelCase     :			List[Any]  							=      False
          __UpperCAmelCase     :			str  							=      set()

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

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

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

     def 			lowerCamelCase__			(    self					:		Any      )						->							Optional[Any]:
          __UpperCAmelCase     :			str  							=      []
          __UpperCAmelCase     :			Optional[Any]  							=      []
          __UpperCAmelCase     :			Optional[int]  							=      list(self.graph      )[0]
          stack.append(snake_case      )
          visited.append(snake_case      )
          __UpperCAmelCase     :			List[Any]  							=      -2
          __UpperCAmelCase     :			List[str]  							=      []
          __UpperCAmelCase     :			Any  							=      s
          __UpperCAmelCase     :			Tuple  							=      False
          __UpperCAmelCase     :			Tuple  							=      set()

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

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

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

     def 			lowerCamelCase__			(    self					:		List[Any]      )						->							Any:
          return list(self.graph      )

     def 			lowerCamelCase__			(    self					:		Optional[Any]							,			snake_case					:		Dict=-2							,			snake_case					:		Dict=-1      )						->							Union[str, Any]:
          __UpperCAmelCase     :			Any  							=      time()
          self.dfs(snake_case							,			snake_case      )
          __UpperCAmelCase     :			str  							=      time()
          return end - begin






     def 			lowerCamelCase__			(    self					:		Optional[int]							,			snake_case					:		str=-2      )						->							str:
          __UpperCAmelCase     :			List[Any]  							=      time()
          self.bfs(snake_case      )
          __UpperCAmelCase     :			List[str]  							=      time()
          return end - begin



'''simple docstring'''



from typing import TYPE_CHECKING

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


__UpperCAmelCase      :Union[str, Any]			    =       {
    "configuration_rag": ["RagConfig"],
    "retrieval_rag": ["RagRetriever"],
    "tokenization_rag": ["RagTokenizer"],
}

try:
      if not is_torch_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      __UpperCAmelCase      :Dict			    =       [
          "RagModel",
          "RagPreTrainedModel",
          "RagSequenceForGeneration",
          "RagTokenForGeneration",
      ]

try:
      if not is_tf_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      __UpperCAmelCase      :Dict			    =       [
          "TFRagModel",
          "TFRagPreTrainedModel",
          "TFRagSequenceForGeneration",
          "TFRagTokenForGeneration",
      ]


if TYPE_CHECKING:
      from .configuration_rag import RagConfig
      from .retrieval_rag import RagRetriever
      from .tokenization_rag import RagTokenizer

      try:
            if not is_torch_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from .modeling_rag import RagModel, RagPreTrainedModel, RagSequenceForGeneration, RagTokenForGeneration

      try:
            if not is_tf_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from .modeling_tf_rag import (
                TFRagModel,
                TFRagPreTrainedModel,
                TFRagSequenceForGeneration,
                TFRagTokenForGeneration,
            )

else:
      import sys

      __UpperCAmelCase      :Any			    =       _LazyModule(__name__, globals()["__file__"], _import_structure, module_spec=__spec__)