



"""simple docstring"""

# using dfs for finding eulerian path traversal









def 							SCREAMING_SNAKE_CASE__      (		SCREAMING_SNAKE_CASE__ :  Tuple				,    SCREAMING_SNAKE_CASE__ :  str				,    SCREAMING_SNAKE_CASE__ :  Union[str, Any]				,    SCREAMING_SNAKE_CASE__ :  Tuple=None			):



					"""simple docstring"""





					snake_case_					:		Union[str, Any] 					=					(path or []) + [u]
					for v in graph[u]:
										if visited_edge[u][v] is False:
															snake_case_					,			snake_case_					:		Optional[Any] 					=					True, True
															snake_case_					:		Optional[int] 					=					dfs(lowerCAmelCase__				,    lowerCAmelCase__				,    lowerCAmelCase__				,    lowerCAmelCase__			)
					return path







def 							SCREAMING_SNAKE_CASE__      (		SCREAMING_SNAKE_CASE__ :  str				,    SCREAMING_SNAKE_CASE__ :  str			):



					"""simple docstring"""





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







def 							SCREAMING_SNAKE_CASE__      (		SCREAMING_SNAKE_CASE__ :  Dict				,    SCREAMING_SNAKE_CASE__ :  List[Any]			):



					"""simple docstring"""





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







def 							SCREAMING_SNAKE_CASE__      (		):



					"""simple docstring"""





					snake_case_					:		Optional[int] 					=					{1: [2, 3, 4], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [4]}
					snake_case_					:		Dict 					=					{1: [2, 3, 4, 5], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [1, 4]}
					snake_case_					:		int 					=					{1: [2, 3, 4], 2: [1, 3, 4], 3: [1, 2], 4: [1, 2, 5], 5: [4]}
					snake_case_					:		List[Any] 					=					{1: [2, 3], 2: [1, 3], 3: [1, 2]}
					snake_case_					:		Any 					=					{
					    1: [],
					    2: []
					    # all degree is zero
					}
					snake_case_					:		int 					=					1_0
					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"""

def 							SCREAMING_SNAKE_CASE__      (		SCREAMING_SNAKE_CASE__ :  list			):



					"""simple docstring"""





					snake_case_					:		Optional[int] 					=					len(SCREAMING_SNAKE_CASE__			)
					for i in range(1				,    SCREAMING_SNAKE_CASE__			):
										snake_case_					:		Tuple 					=					collection[i]
										snake_case_					:		Tuple 					=					0
										snake_case_					:		str 					=					i - 1

										while low <= high:
															snake_case_					:		Optional[int] 					=					(low + high) // 2
															if val < collection[mid]:
																				snake_case_					:		List[str] 					=					mid - 1
															else:
																				snake_case_					:		str 					=					mid + 1
										for j in range(SCREAMING_SNAKE_CASE__				,    SCREAMING_SNAKE_CASE__				,    -1			):
															snake_case_					:		List[str] 					=					collection[j - 1]
										snake_case_					:		Any 					=					val
					return collection


if __name__ == "__main__":
			a_			   =					input('''Enter numbers separated by a comma:\n''').strip()
			a_			   =					[int(item) for item in user_input.split(''',''')]
			print(binary_insertion_sort(unsorted))




