





'''simple docstring'''

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







class __a			:





   def __init__(       self					:      Tuple     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							{}





   def   UpperCAmelCase__  (       self					:      Optional[Any]					,lowerCamelCase					:      List[Any]					,lowerCamelCase					:      Dict					,lowerCamelCase					:      Optional[Any]=1     ):

      '''simple docstring'''

      if self.graph.get(lowerCamelCase     ):
         if self.graph[u].count([w, v]     ) == 0:
            self.graph[u].append([w, v]     )
      else:
         __SCREAMING_SNAKE_CASE   				=							[[w, v]]
      if not self.graph.get(lowerCamelCase     ):
         __SCREAMING_SNAKE_CASE   				=							[]





   def   UpperCAmelCase__  (       self					:      Optional[int]     ):

      '''simple docstring'''

      return list(self.graph     )





   def   UpperCAmelCase__  (       self					:      Optional[Any]					,lowerCamelCase					:      Tuple					,lowerCamelCase					:      Optional[Any]     ):

      '''simple docstring'''

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





   def   UpperCAmelCase__  (       self					:      Tuple					,lowerCamelCase					:      Any=-2					,lowerCamelCase					:      Optional[Any]=-1     ):

      '''simple docstring'''

      if s == d:
         return []
      __SCREAMING_SNAKE_CASE   				=							[]
      __SCREAMING_SNAKE_CASE   				=							[]
      if s == -2:
         __SCREAMING_SNAKE_CASE   				=							list(self.graph     )[0]
      stack.append(lowerCamelCase     )
      visited.append(lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							s

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

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

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





   def   UpperCAmelCase__  (       self					:      str					,lowerCamelCase					:      str=-1     ):

      '''simple docstring'''

      if c == -1:
         __SCREAMING_SNAKE_CASE   				=							floor(random() * 1_0000     ) + 10
      for i in range(lowerCamelCase     ):
         # every vertex has max 100 edges
         for _ in range(floor(random() * 102     ) + 1     ):
            __SCREAMING_SNAKE_CASE   				=							floor(random() * c     ) + 1
            if n != i:
               self.add_pair(lowerCamelCase					,lowerCamelCase					,1     )





   def   UpperCAmelCase__  (       self					:      Any					,lowerCamelCase					:      str=-2     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							deque()
      __SCREAMING_SNAKE_CASE   				=							[]
      if s == -2:
         __SCREAMING_SNAKE_CASE   				=							list(self.graph     )[0]
      d.append(lowerCamelCase     )
      visited.append(lowerCamelCase     )
      while d:
         __SCREAMING_SNAKE_CASE   				=							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   UpperCAmelCase__  (       self					:      Union[str, Any]					,lowerCamelCase					:      Dict     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							0
      for x in self.graph:
         for y in self.graph[x]:
            if y[1] == u:
               count += 1
      return count





   def   UpperCAmelCase__  (       self					:      List[Any]					,lowerCamelCase					:      Optional[int]     ):

      '''simple docstring'''

      return len(self.graph[u]     )





   def   UpperCAmelCase__  (       self					:      Union[str, Any]					,lowerCamelCase					:      List[Any]=-2     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							[]
      __SCREAMING_SNAKE_CASE   				=							[]
      if s == -2:
         __SCREAMING_SNAKE_CASE   				=							list(self.graph     )[0]
      stack.append(lowerCamelCase     )
      visited.append(lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							s
      __SCREAMING_SNAKE_CASE   				=							[]

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

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

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





   def   UpperCAmelCase__  (       self					:      Any     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							[]
      __SCREAMING_SNAKE_CASE   				=							[]
      __SCREAMING_SNAKE_CASE   				=							list(self.graph     )[0]
      stack.append(lowerCamelCase     )
      visited.append(lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							-2
      __SCREAMING_SNAKE_CASE   				=							[]
      __SCREAMING_SNAKE_CASE   				=							s
      __SCREAMING_SNAKE_CASE   				=							False
      __SCREAMING_SNAKE_CASE   				=							set()

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

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

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





   def   UpperCAmelCase__  (       self					:      Tuple     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							[]
      __SCREAMING_SNAKE_CASE   				=							[]
      __SCREAMING_SNAKE_CASE   				=							list(self.graph     )[0]
      stack.append(lowerCamelCase     )
      visited.append(lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							-2
      __SCREAMING_SNAKE_CASE   				=							[]
      __SCREAMING_SNAKE_CASE   				=							s
      __SCREAMING_SNAKE_CASE   				=							False
      __SCREAMING_SNAKE_CASE   				=							set()

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

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

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





   def   UpperCAmelCase__  (       self					:      Any					,lowerCamelCase					:      Dict=-2					,lowerCamelCase					:      Any=-1     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							time()
      self.dfs(lowerCamelCase					,lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							time()
      return end - begin





   def   UpperCAmelCase__  (       self					:      Tuple					,lowerCamelCase					:      Any=-2     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							time()
      self.bfs(lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							time()
      return end - begin







class __a			:





   def __init__(       self					:      Tuple     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							{}





   def   UpperCAmelCase__  (       self					:      str					,lowerCamelCase					:      Any					,lowerCamelCase					:      Optional[int]					,lowerCamelCase					:      int=1     ):

      '''simple docstring'''

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





   def   UpperCAmelCase__  (       self					:      Dict					,lowerCamelCase					:      str					,lowerCamelCase					:      Union[str, Any]     ):

      '''simple docstring'''

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





   def   UpperCAmelCase__  (       self					:      List[str]					,lowerCamelCase					:      Any=-2					,lowerCamelCase					:      Tuple=-1     ):

      '''simple docstring'''

      if s == d:
         return []
      __SCREAMING_SNAKE_CASE   				=							[]
      __SCREAMING_SNAKE_CASE   				=							[]
      if s == -2:
         __SCREAMING_SNAKE_CASE   				=							list(self.graph     )[0]
      stack.append(lowerCamelCase     )
      visited.append(lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							s

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

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

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





   def   UpperCAmelCase__  (       self					:      Union[str, Any]					,lowerCamelCase					:      List[str]=-1     ):

      '''simple docstring'''

      if c == -1:
         __SCREAMING_SNAKE_CASE   				=							floor(random() * 1_0000     ) + 10
      for i in range(lowerCamelCase     ):
         # every vertex has max 100 edges
         for _ in range(floor(random() * 102     ) + 1     ):
            __SCREAMING_SNAKE_CASE   				=							floor(random() * c     ) + 1
            if n != i:
               self.add_pair(lowerCamelCase					,lowerCamelCase					,1     )





   def   UpperCAmelCase__  (       self					:      int					,lowerCamelCase					:      List[Any]=-2     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							deque()
      __SCREAMING_SNAKE_CASE   				=							[]
      if s == -2:
         __SCREAMING_SNAKE_CASE   				=							list(self.graph     )[0]
      d.append(lowerCamelCase     )
      visited.append(lowerCamelCase     )
      while d:
         __SCREAMING_SNAKE_CASE   				=							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   UpperCAmelCase__  (       self					:      Optional[int]					,lowerCamelCase					:      Optional[Any]     ):

      '''simple docstring'''

      return len(self.graph[u]     )





   def   UpperCAmelCase__  (       self					:      Dict     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							[]
      __SCREAMING_SNAKE_CASE   				=							[]
      __SCREAMING_SNAKE_CASE   				=							list(self.graph     )[0]
      stack.append(lowerCamelCase     )
      visited.append(lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							-2
      __SCREAMING_SNAKE_CASE   				=							[]
      __SCREAMING_SNAKE_CASE   				=							s
      __SCREAMING_SNAKE_CASE   				=							False
      __SCREAMING_SNAKE_CASE   				=							set()

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

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

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





   def   UpperCAmelCase__  (       self					:      Dict     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							[]
      __SCREAMING_SNAKE_CASE   				=							[]
      __SCREAMING_SNAKE_CASE   				=							list(self.graph     )[0]
      stack.append(lowerCamelCase     )
      visited.append(lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							-2
      __SCREAMING_SNAKE_CASE   				=							[]
      __SCREAMING_SNAKE_CASE   				=							s
      __SCREAMING_SNAKE_CASE   				=							False
      __SCREAMING_SNAKE_CASE   				=							set()

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

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

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





   def   UpperCAmelCase__  (       self					:      str     ):

      '''simple docstring'''

      return list(self.graph     )





   def   UpperCAmelCase__  (       self					:      str					,lowerCamelCase					:      int=-2					,lowerCamelCase					:      List[str]=-1     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							time()
      self.dfs(lowerCamelCase					,lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							time()
      return end - begin





   def   UpperCAmelCase__  (       self					:      Tuple					,lowerCamelCase					:      List[str]=-2     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							time()
      self.bfs(lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							time()
      return end - begin












'''simple docstring'''

def    a__							(							lowercase   :	Dict,   lowercase   :	Optional[Any] )						->						int:





     """simple docstring"""

     _UpperCamelCase							       =			0
     _UpperCamelCase							       =			len(lowercase ) - 1

     while left <= right:
          # avoid divided by 0 during interpolation
          if sorted_collection[left] == sorted_collection[right]:
               if sorted_collection[left] == item:
                    return left
               else:
                    return None

          _UpperCamelCase							       =			left + ((item - sorted_collection[left]) * (right - left)) // (
              sorted_collection[right] - sorted_collection[left]
          )

          # out of range check
          if point < 0 or point >= len(lowercase ):
               return None

          _UpperCamelCase							       =			sorted_collection[point]
          if current_item == item:
               return point
          else:
               if point < left:
                    _UpperCamelCase							       =			left
                    _UpperCamelCase							       =			point
               elif point > right:
                    _UpperCamelCase							       =			right
                    _UpperCamelCase							       =			point
               else:
                    if item < current_item:
                         _UpperCamelCase							       =			point - 1
                    else:
                         _UpperCamelCase							       =			point + 1
     return None







def    a__							(							lowercase   :	int,   lowercase   :	Optional[int],   lowercase   :	List[Any],   lowercase   :	List[Any] )						->						Dict:





     """simple docstring"""

     if sorted_collection[left] == sorted_collection[right]:
          if sorted_collection[left] == item:
               return left
          else:
               return None

     _UpperCamelCase							       =			left + ((item - sorted_collection[left]) * (right - left)) // (
         sorted_collection[right] - sorted_collection[left]
     )

     # out of range check
     if point < 0 or point >= len(lowercase ):
          return None

     if sorted_collection[point] == item:
          return point
     elif point < left:
          return interpolation_search_by_recursion(lowercase,   lowercase,   lowercase,   lowercase )
     elif point > right:
          return interpolation_search_by_recursion(lowercase,   lowercase,   lowercase,   lowercase )
     else:
          if sorted_collection[point] > item:
               return interpolation_search_by_recursion(
                   lowercase,   lowercase,   lowercase,   point - 1 )
          else:
               return interpolation_search_by_recursion(
                   lowercase,   lowercase,   point + 1,   lowercase )







def    a__							(							lowercase   :	Any )						->						List[Any]:





     """simple docstring"""

     if collection != sorted(lowercase ):
          raise ValueError('''Collection must be ascending sorted''' )
     return True


if __name__ == "__main__":
   import sys
   lowercase__		:     int			=							0
   if debug == 1:
      lowercase__		:     Optional[Any]			=							[10, 30, 40, 45, 50, 66, 77, 93]
      try:
         __assert_sorted(collection)
      except ValueError:
         sys.exit('Sequence must be ascending sorted to apply interpolation search')
      lowercase__		:     List[str]			=							67

   lowercase__		:     Optional[int]			=							interpolation_search(collection, target)
   if result is not None:
      print(F"""{target} found at positions: {result}""")
   else:
      print('Not found')



