


"""simple docstring"""


def _lowerCamelCase			(	_UpperCamelCase					,				_UpperCamelCase					,				_UpperCamelCase					,				_UpperCamelCase=None   ):

			'''simple docstring'''




			__lowerCAmelCase       					=    (path or []) + [u]
			for v in graph[u]:
						if visited_edge[u][v] is False:
									__lowerCAmelCase					,			__lowerCAmelCase       					=    True, True
									__lowerCAmelCase       					=    dfs(lowerCAmelCase__					,				lowerCAmelCase__					,				lowerCAmelCase__					,				lowerCAmelCase__   )
			return path


def _lowerCamelCase			(	_UpperCamelCase					,				_UpperCamelCase   ):

			'''simple docstring'''




			__lowerCAmelCase       					=    0
			__lowerCAmelCase       					=    -1
			for i in range(lowerCAmelCase__   ):
						if i not in graph.keys():
									continue
						if len(graph[i]   ) % 2 == 1:
									odd_degree_nodes += 1
									__lowerCAmelCase       					=    i
			if odd_degree_nodes == 0:
						return 1, odd_node
			if odd_degree_nodes == 2:
						return 2, odd_node
			return 3, odd_node


def _lowerCamelCase			(	_UpperCamelCase					,				_UpperCamelCase   ):

			'''simple docstring'''




			__lowerCAmelCase       					=    [[False for _ in range(max_node + 1   )] for _ in range(max_node + 1   )]
			__lowerCAmelCase					,			__lowerCAmelCase       					=    check_circuit_or_path(lowerCAmelCase__					,				lowerCAmelCase__   )
			if check == 3:
						print("graph is not Eulerian"   )
						print("no path"   )
						return
			__lowerCAmelCase       					=    1
			if check == 2:
						__lowerCAmelCase       					=    odd_node
						print("graph has a Euler path"   )
			if check == 1:
						print("graph has a Euler cycle"   )
			__lowerCAmelCase       					=    dfs(lowerCAmelCase__					,				lowerCAmelCase__					,				lowerCAmelCase__   )
			print(lowerCAmelCase__   )


def _lowerCamelCase			(	):

			'''simple docstring'''




			__lowerCAmelCase       					=    {1: [2, 3, 4], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [4]}
			__lowerCAmelCase       					=    {1: [2, 3, 4, 5], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [1, 4]}
			__lowerCAmelCase       					=    {1: [2, 3, 4], 2: [1, 3, 4], 3: [1, 2], 4: [1, 2, 5], 5: [4]}
			__lowerCAmelCase       					=    {1: [2, 3], 2: [1, 3], 3: [1, 2]}
			__lowerCAmelCase       					=    {
			    1: [],
			    2: []
			    # all degree is zero
			}
			__lowerCAmelCase       					=    10
			check_euler(lowerCAmelCase__					,				lowerCAmelCase__   )
			check_euler(lowerCAmelCase__					,				lowerCAmelCase__   )
			check_euler(lowerCAmelCase__					,				lowerCAmelCase__   )
			check_euler(lowerCAmelCase__					,				lowerCAmelCase__   )
			check_euler(lowerCAmelCase__					,				lowerCAmelCase__   )


if __name__ == "__main__":
	main()




"""simple docstring"""


A  :     List[Any]    					=    [4, 1, 7, 4, 2, 6, 4, 1, 5, 3, 7, 5]
A  :     Optional[int]    					=    [3, 7, 7, 4, 2, 6, 4, 1, 5, 3, 7, 5]
A  :     Optional[int]    					=    {
    0: "Sunday",
    1: "Monday",
    2: "Tuesday",
    3: "Wednesday",
    4: "Thursday",
    5: "Friday",
    6: "Saturday",
}


def _lowerCamelCase			(	_UpperCamelCase					,				_UpperCamelCase					,				_UpperCamelCase   ):

			'''simple docstring'''




			assert len(str(_UpperCamelCase   )   ) > 2, "year should be in YYYY format"
			assert 1 <= month <= 12, "month should be between 1 to 12"
			assert 1 <= day <= 31, "day should be between 1 to 31"

			# Doomsday algorithm:
			__lowerCAmelCase       					=    year // 100
			__lowerCAmelCase       					=    (5 * (century % 4) + 2) % 7
			__lowerCAmelCase       					=    year % 100
			__lowerCAmelCase       					=    centurian % 12
			__lowerCAmelCase       					=    (
			    (centurian // 12) + centurian_m + (centurian_m // 4) + century_anchor
			) % 7
			__lowerCAmelCase       					=    (
			    DOOMSDAY_NOT_LEAP[month - 1]
			    if (year % 4 != 0) or (centurian == 0 and (year % 400) == 0)
			    else DOOMSDAY_LEAP[month - 1]
			)
			__lowerCAmelCase       					=    (dooms_day + day - day_anchor) % 7
			return WEEK_DAY_NAMES[week_day]


if __name__ == "__main__":
	import doctest

	doctest.testmod()




