


# using dfs for finding eulerian path traversal






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE=None      )->						Optional[Any]:




      """simple docstring"""

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






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      )->						Union[str, Any]:




      """simple docstring"""

      snake_case_ =   0
      snake_case_ =   -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
                  snake_case_ =   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					(SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      )->						Dict:




      """simple docstring"""

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






def  __lowerCAmelCase					()->						Union[str, Any]:




      """simple docstring"""

      snake_case_ =   {1: [2, 3, 4], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [4]}
      snake_case_ =   {1: [2, 3, 4, 5], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [1, 4]}
      snake_case_ =   {1: [2, 3, 4], 2: [1, 3, 4], 3: [1, 2], 4: [1, 2, 5], 5: [4]}
      snake_case_ =   {1: [2, 3], 2: [1, 3], 3: [1, 2]}
      snake_case_ =   {
          1: [],
          2: []
          # all degree is zero
      }
      snake_case_ =   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      )->						int:




      """simple docstring"""

      assert column_title.isupper()
      snake_case_ =   0
      snake_case_ =   len(SCREAMING_SNAKE_CASE      ) - 1
      snake_case_ =   0

      while index >= 0:
            snake_case_ =   (ord(column_title[index]      ) - 64) * pow(26      ,      SCREAMING_SNAKE_CASE      )
            answer += value
            power += 1
            index -= 1

      return answer


if __name__ == "__main__":
   from doctest import testmod

   testmod()