


'''simple docstring'''

a_						:       List[Any]      			=				{0: [2, 3], 1: [0], 2: [1], 3: [4], 4: []}

a_						:       Tuple      			=				{0: [1, 2, 3], 1: [2], 2: [0], 3: [4], 4: [5], 5: [3]}





def __snake_case      (   UpperCAmelCase_		:		dict[int, list[int]]      ,       UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		list[bool]					):
 lowerCamelCase_  				=						True
 lowerCamelCase_  				=						[]

 for neighbour in graph[vert]:
  if not visited[neighbour]:
   order += topology_sort(UpperCAmelCase_      ,       UpperCAmelCase_      ,       UpperCAmelCase_					)

 order.append(UpperCAmelCase_					)

 return order





def __snake_case      (   UpperCAmelCase_		:		dict[int, list[int]]      ,       UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		list[bool]					):
 lowerCamelCase_  				=						True
 lowerCamelCase_  				=						[vert]

 for neighbour in reversed_graph[vert]:
  if not visited[neighbour]:
   component += find_components(UpperCAmelCase_      ,       UpperCAmelCase_      ,       UpperCAmelCase_					)

 return component







def __snake_case      (   UpperCAmelCase_		:		dict[int, list[int]]					):
 lowerCamelCase_  				=						len(UpperCAmelCase_					) * [False]
 lowerCamelCase_  				=						{vert: [] for vert in range(len(UpperCAmelCase_					)					)}

 for vert, neighbours in graph.items():
  for neighbour in neighbours:
   reversed_graph[neighbour].append(UpperCAmelCase_					)

 lowerCamelCase_  				=						[]
 for i, was_visited in enumerate(UpperCAmelCase_					):
  if not was_visited:
   order += topology_sort(UpperCAmelCase_      ,       UpperCAmelCase_      ,       UpperCAmelCase_					)

 lowerCamelCase_  				=						[]
 lowerCamelCase_  				=						len(UpperCAmelCase_					) * [False]

 for i in range(len(UpperCAmelCase_					)					):
  lowerCamelCase_  				=						order[len(UpperCAmelCase_					) - i - 1]
  if not visited[vert]:
   lowerCamelCase_  				=						find_components(UpperCAmelCase_      ,       UpperCAmelCase_      ,       UpperCAmelCase_					)
   components_list.append(UpperCAmelCase_					)

 return components_list







'''simple docstring'''

from __future__ import annotations





def __snake_case      (   UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		int	):
 if b == 0:
  return (1, 0)
 ((lowerCamelCase_)				,(lowerCamelCase_))  				=						extended_euclid(UpperCAmelCase_      ,       a % b	)
 lowerCamelCase_  				=						a // b
 return (y, x - k * y)





def __snake_case      (   UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		int	):
 ((lowerCamelCase_)				,(lowerCamelCase_))  				=						extended_euclid(UpperCAmelCase_      ,       UpperCAmelCase_	)
 lowerCamelCase_  				=						na * na
 lowerCamelCase_  				=						ra * x * na + ra * y * na
 return (n % m + m) % m





def __snake_case      (   UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		int	):
 ((lowerCamelCase_)				,(lowerCamelCase_))  				=						extended_euclid(UpperCAmelCase_      ,       UpperCAmelCase_	)
 if b < 0:
  lowerCamelCase_  				=						(b % n + n) % n
 return b





def __snake_case      (   UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		int      ,       UpperCAmelCase_		:		int	):
 lowerCamelCase_				,lowerCamelCase_  				=						invert_modulo(UpperCAmelCase_      ,       UpperCAmelCase_	), invert_modulo(UpperCAmelCase_      ,       UpperCAmelCase_	)
 lowerCamelCase_  				=						na * na
 lowerCamelCase_  				=						ra * x * na + ra * y * na
 return (n % m + m) % m


if __name__ == "__main__":
     from doctest import testmod

     testmod(name="""chinese_remainder_theorem""", verbose=True)
     testmod(name="""chinese_remainder_theorem2""", verbose=True)
     testmod(name="""invert_modulo""", verbose=True)
     testmod(name="""extended_euclid""", verbose=True)



