





'''simple docstring'''


# using dfs for finding eulerian path traversal
def       __snake_case		( SCREAMING_SNAKE_CASE_ :			Optional[int]			,	SCREAMING_SNAKE_CASE_ :			int			,	SCREAMING_SNAKE_CASE_ :			Tuple			,	SCREAMING_SNAKE_CASE_ :			List[str]=None )							->     List[Any]:

       """simple docstring"""


       UpperCAmelCase  =						(path or []) + [u]
       for v in graph[u]:
              if visited_edge[u][v] is False:
                     UpperCAmelCase,					UpperCAmelCase  =						True, True
                     UpperCAmelCase  =						dfs(SCREAMING_SNAKE_CASE_			,	SCREAMING_SNAKE_CASE_			,	SCREAMING_SNAKE_CASE_			,	SCREAMING_SNAKE_CASE_ )
       return path
def       __snake_case		( SCREAMING_SNAKE_CASE_ :			Any			,	SCREAMING_SNAKE_CASE_ :			Tuple )							->     Any:

       """simple docstring"""


       UpperCAmelCase  =						0
       UpperCAmelCase  =						-1
       for i in range(SCREAMING_SNAKE_CASE_ ):
              if i not in graph.keys():
                     continue
              if len(graph[i] ) % 2 == 1:
                     odd_degree_nodes += 1
                     UpperCAmelCase  =						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		( SCREAMING_SNAKE_CASE_ :			int			,	SCREAMING_SNAKE_CASE_ :			List[Any] )							->     List[str]:

       """simple docstring"""


       UpperCAmelCase  =						[[False for _ in range(max_node + 1 )] for _ in range(max_node + 1 )]
       UpperCAmelCase,					UpperCAmelCase  =						check_circuit_or_path(SCREAMING_SNAKE_CASE_			,	SCREAMING_SNAKE_CASE_ )
       if check == 3:
              print('''graph is not Eulerian''' )
              print('''no path''' )
              return
       UpperCAmelCase  =						1
       if check == 2:
              UpperCAmelCase  =						odd_node
              print('''graph has a Euler path''' )
       if check == 1:
              print('''graph has a Euler cycle''' )
       UpperCAmelCase  =						dfs(SCREAMING_SNAKE_CASE_			,	SCREAMING_SNAKE_CASE_			,	SCREAMING_SNAKE_CASE_ )
       print(SCREAMING_SNAKE_CASE_ )
def       __snake_case		( )							->     Union[str, Any]:

       """simple docstring"""


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


if __name__ == "__main__":
    main()









def 				__lowerCAmelCase(       _SCREAMING_SNAKE_CASE							,     _SCREAMING_SNAKE_CASE				)							-> int:




    """simple docstring"""




    return int((input_a, input_a).count(0				) != 0				)





def 				__lowerCAmelCase(       )							-> None:




    """simple docstring"""




    assert nand_gate(0							,     0				) == 1
    assert nand_gate(0							,     1				) == 1
    assert nand_gate(1							,     0				) == 1
    assert nand_gate(1							,     1				) == 0


if __name__ == "__main__":
 print(nand_gate(0, 0))
 print(nand_gate(0, 1))
 print(nand_gate(1, 0))
 print(nand_gate(1, 1))





