


'''simple docstring'''



# using dfs for finding eulerian path traversal




def 			_a			(		_lowercase      :			Optional[Any]    ,      _lowercase      :			List[str]    ,      _lowercase      :			List[str]    ,      _lowercase      :			Optional[Any]=None						):





     '''simple docstring'''






     __UpperCAmelCase			:				Any													=    (path or []) + [u]
     for v in graph[u]:
          if visited_edge[u][v] is False:
               __UpperCAmelCase							,     __UpperCAmelCase			:				Dict													=    True, True
               __UpperCAmelCase			:				Any													=    dfs(_lowercase    ,      _lowercase    ,      _lowercase    ,      _lowercase						)
     return path




def 			_a			(		_lowercase      :			int    ,      _lowercase      :			Tuple						):





     '''simple docstring'''






     __UpperCAmelCase			:				List[Any]													=    0
     __UpperCAmelCase			:				Dict													=    -1
     for i in range(_lowercase						):
          if i not in graph.keys():
               continue
          if len(graph[i]						) % 2 == 1:
               odd_degree_nodes += 1
               __UpperCAmelCase			:				int													=    i
     if odd_degree_nodes == 0:
          return 1, odd_node
     if odd_degree_nodes == 2:
          return 2, odd_node
     return 3, odd_node




def 			_a			(		_lowercase      :			Dict    ,      _lowercase      :			List[str]						):





     '''simple docstring'''






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




def 			_a			(		):





     '''simple docstring'''






     __UpperCAmelCase			:				Optional[int]													=    {1: [2, 3, 4], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [4]}
     __UpperCAmelCase			:				int													=    {1: [2, 3, 4, 5], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [1, 4]}
     __UpperCAmelCase			:				Any													=    {1: [2, 3, 4], 2: [1, 3, 4], 3: [1, 2], 4: [1, 2, 5], 5: [4]}
     __UpperCAmelCase			:				Union[str, Any]													=    {1: [2, 3], 2: [1, 3], 3: [1, 2]}
     __UpperCAmelCase			:				str													=    {
         1: [],
         2: []
         # all degree is zero
     }
     __UpperCAmelCase			:				str													=    10
     check_euler(_lowercase    ,      _lowercase						)
     check_euler(_lowercase    ,      _lowercase						)
     check_euler(_lowercase    ,      _lowercase						)
     check_euler(_lowercase    ,      _lowercase						)
     check_euler(_lowercase    ,      _lowercase						)


if __name__ == "__main__":
      main()



'''simple docstring'''



def 			_a			(		_lowercase      :			int = 50000000						):





     '''simple docstring'''






     __UpperCAmelCase			:				List[str]													=    set()
     __UpperCAmelCase			:				Tuple													=    int((limit - 24) ** (1 / 2)						)

     __UpperCAmelCase			:				Tuple													=    set(range(3    ,      prime_square_limit + 1    ,      2						)						)
     primes.add(2						)
     for p in range(3    ,      prime_square_limit + 1    ,      2						):
          if p not in primes:
               continue
          primes.difference_update(set(range(p * p    ,      prime_square_limit + 1    ,      _lowercase						)						)						)

     for primea in primes:
          __UpperCAmelCase			:				Any													=    primea * primea
          for primea in primes:
               __UpperCAmelCase			:				Any													=    primea * primea * primea
               if square + cube >= limit - 16:
                    break
               for primea in primes:
                    __UpperCAmelCase			:				Optional[Any]													=    primea * primea * primea * primea
                    __UpperCAmelCase			:				Union[str, Any]													=    square + cube + tetr
                    if total >= limit:
                         break
                    ret.add(_lowercase						)

     return len(_lowercase						)


if __name__ == "__main__":
      print(f"""{solution() = }""")