

from __future__ import annotations

from collections import Counter
from random import random






class _UpperCamelCase							:
			'''simple docstring'''







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

				"""simple docstring"""

				SCREAMING_SNAKE_CASE   :      Optional[Any]				     =       {}
			def 							__UpperCamelCase (			self							: Dict      ,      a							: str	)							->       None:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE   :      List[str]				     =       {}
			def 							__UpperCamelCase (			self							: Union[str, Any]      ,      a							: str      ,      a							: str      ,      a							: float	)							->       None:

				"""simple docstring"""

				if nodea not in self.connections:
					self.add_node(a	)
				if nodea not in self.connections:
					self.add_node(a	)
				SCREAMING_SNAKE_CASE   :      str				     =       probability
			def 							__UpperCamelCase (			self							: Any	)							->       list[str]:

				"""simple docstring"""

				return list(self.connections	)






			def 							__UpperCamelCase (			self							: List[str]      ,      a							: str	)							->       str:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE   :      Tuple				     =       0
				SCREAMING_SNAKE_CASE   :      Optional[Any]				     =       random()

				for dest in self.connections[node]:
					current_probability += self.connections[node][dest]
					if current_probability > random_value:
						return dest
				return ""

def  lowerCamelCase__ (					_a							,			_a							,			_a):
	SCREAMING_SNAKE_CASE   :      Any				     =       MarkovChainGraphUndirectedUnweighted()

	for nodea, nodea, probability in transitions:
		graph.add_transition_probability(_a							,			_a							,			_a)

	SCREAMING_SNAKE_CASE   :      List[str]				     =       Counter(graph.get_nodes())
	SCREAMING_SNAKE_CASE   :      Optional[Any]				     =       start

	for _ in range(_a):
		SCREAMING_SNAKE_CASE   :      List[str]				     =       graph.transition(_a)
		visited[node] += 1

	return visited


if __name__ == "__main__":
			import doctest

			doctest.testmod()


from __future__ import annotations

def  lowerCamelCase__ (					_a							,			_a):
	if b == 0:
		return (1, 0)
	((SCREAMING_SNAKE_CASE)     ,(SCREAMING_SNAKE_CASE))   :      Tuple				     =       extended_euclid(_a							,			a % b)
	SCREAMING_SNAKE_CASE   :      Dict				     =       a // b
	return (y, x - k * y)

def  lowerCamelCase__ (					_a							,			_a							,			_a							,			_a):
	((SCREAMING_SNAKE_CASE)     ,(SCREAMING_SNAKE_CASE))   :      str				     =       extended_euclid(_a							,			_a)
	SCREAMING_SNAKE_CASE   :      str				     =       na * na
	SCREAMING_SNAKE_CASE   :      int				     =       ra * x * na + ra * y * na
	return (n % m + m) % m

def  lowerCamelCase__ (					_a							,			_a):
	((SCREAMING_SNAKE_CASE)     ,(SCREAMING_SNAKE_CASE))   :      List[str]				     =       extended_euclid(_a							,			_a)
	if b < 0:
		SCREAMING_SNAKE_CASE   :      int				     =       (b % n + n) % n
	return b

def  lowerCamelCase__ (					_a							,			_a							,			_a							,			_a):
	SCREAMING_SNAKE_CASE     ,SCREAMING_SNAKE_CASE   :      Dict				     =       invert_modulo(_a							,			_a), invert_modulo(_a							,			_a)
	SCREAMING_SNAKE_CASE   :      Optional[int]				     =       na * na
	SCREAMING_SNAKE_CASE   :      Optional[Any]				     =       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)