




"""simple docstring"""


def 					UpperCAmelCase__       (snake_case__							:					Optional[Any]		,   snake_case__							:					Any    ):
  """simple docstring"""

  _snake_case							:		str								=  0
  _snake_case							:		Any								=  len(__snake_case    ) - 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

    _snake_case							:		Union[str, Any]								=  left + ((item - sorted_collection[left]) * (right - left)) // (
        sorted_collection[right] - sorted_collection[left]
    )

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

    _snake_case							:		Any								=  sorted_collection[point]
    if current_item == item:
      return point
    else:
      if point < left:
        _snake_case							:		Optional[Any]								=  left
        _snake_case							:		List[str]								=  point
      elif point > right:
        _snake_case							:		Tuple								=  right
        _snake_case							:		List[str]								=  point
      else:
        if item < current_item:
          _snake_case							:		Dict								=  point - 1
        else:
          _snake_case							:		str								=  point + 1
  return None


def 					UpperCAmelCase__       (snake_case__							:					Optional[int]		,   snake_case__							:					Tuple		,   snake_case__							:					Optional[int]		,   snake_case__							:					List[str]    ):
  """simple docstring"""

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

  _snake_case							:		List[str]								=  left + ((item - sorted_collection[left]) * (right - left)) // (
      sorted_collection[right] - sorted_collection[left]
  )

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

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


def 					UpperCAmelCase__       (snake_case__							:					Union[str, Any]    ):
  """simple docstring"""

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


if __name__ == "__main__":
     import sys
     A_						=				0
     if debug == 1:
          A_						=				[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''')
          A_						=				67

     A_						=				interpolation_search(collection, target)
     if result is not None:
          print(F'''{target} found at positions: {result}''')
     else:
          print('''Not found''')




"""simple docstring"""





class     _UpperCAmelCase:



		def __init__(					self)       ->       Optional[Any]:






							'''simple docstring'''
							_UpperCamelCase							 =  {}



		def 						UpperCAmelCase							(					self)       ->       None:






							'''simple docstring'''
							print(self.vertex)
							for i in self.vertex:
												print(__a				,		''' -> '''				,		''' -> '''.join([str(__a) for j in self.vertex[i]]))



		def 						UpperCAmelCase							(					self				,		__a				,		__a)       ->       None:






							'''simple docstring'''
							# check if vertex is already present,
							if from_vertex in self.vertex:
												self.vertex[from_vertex].append(__a)
							else:
												# else make a new vertex
												_UpperCamelCase							 =  [to_vertex]



		def 						UpperCAmelCase							(					self)       ->       None:






							'''simple docstring'''
							# visited array for storing already visited nodes
							_UpperCamelCase							 =  [False] * len(self.vertex)

							# call the recursive helper function
							for i in range(len(self.vertex)):
												if not visited[i]:
																	self.dfs_recursive(__a				,		__a)




		def 						UpperCAmelCase							(					self				,		__a				,		__a)       ->       None:






							'''simple docstring'''
							# mark start vertex as visited
							_UpperCamelCase							 =  True

							print(__a				,		end=''' ''')

							# Recur for all the vertices that are adjacent to this node
							for i in self.vertex:
												if not visited[i]:
																	self.dfs_recursive(__a				,		__a)


if __name__ == "__main__":
				_a														=		Graph()
				g.add_edge(0, 1)
				g.add_edge(0, 2)
				g.add_edge(1, 2)
				g.add_edge(2, 0)
				g.add_edge(2, 3)
				g.add_edge(3, 3)

				g.print_graph()
				print("""DFS:""")
				g.dfs()

				# OUTPUT:
				# 0  ->  1 -> 2
				# 1  ->  2
				# 2  ->  0 -> 3
				# 3  ->  3
				# DFS:
				#  0 1 2 3






