





# using dfs for finding eulerian path traversal





def     snake_case							(UpperCamelCase			:     Union[str, Any]			,    UpperCamelCase			:     Dict			,    UpperCamelCase			:     Optional[int]			,    UpperCamelCase			:     List[Any]=None							):




	'''simple docstring'''







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

def     snake_case							(UpperCamelCase			:     Union[str, Any]			,    UpperCamelCase			:     List[str]							):




	'''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     snake_case							(UpperCamelCase			:     Optional[Any]			,    UpperCamelCase			:     int							):




	'''simple docstring'''







	lowerCamelCase__										=			[[False for _ in range(max_node + 1							)] for _ in range(max_node + 1							)]
	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     snake_case							():




	'''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()


def       _SCREAMING_SNAKE_CASE   (						_lowerCamelCase					:     int)   ->       int:






							'''simple docstring'''





							__UpperCamelCase      :  Tuple       =   1
							for i in range(1		,    num + 1):
														fact *= i
							return fact




def       _SCREAMING_SNAKE_CASE   (						_lowerCamelCase					:     int)   ->       int:






							'''simple docstring'''





							__UpperCamelCase      :  Dict       =   0
							while number > 0:
														__UpperCamelCase      :  List[Any]       =   number % 10
														sum_of_digits += last_digit
														__UpperCamelCase      :  List[Any]       =   number // 10  # Removing the last_digit from the given number
							return sum_of_digits




def       _SCREAMING_SNAKE_CASE   (						_lowerCamelCase					:     int = 100)   ->       int:






							'''simple docstring'''





							__UpperCamelCase      :  Optional[Any]       =   factorial(_lowerCamelCase)
							__UpperCamelCase      :  Tuple       =   split_and_add(_lowerCamelCase)
							return result


if __name__ == "__main__":
		print(solution(int(input('Enter the Number: ').strip())))