



'''simple docstring'''


def  UpperCAmelCase_       (		lowercase__       ,	lowercase__       ,	lowercase__       ,	lowercase__       ):


     '''simple docstring'''







     if graph[path[curr_ind - 1]][next_ver] == 0:
          return False

     # 2. Validate that next vertex is not already in path
     return not any(vertex == next_ver for vertex in path       )






def  UpperCAmelCase_       (		lowercase__       ,	lowercase__       ,	lowercase__       ):


     '''simple docstring'''







     if curr_ind == len(lowercase__       ):
          # return whether path exists between current and starting vertices
          return graph[path[curr_ind - 1]][path[0]] == 1

     # Recursive Step
     for next_ver in range(0       ,	len(lowercase__       )       ):
          if valid_connection(lowercase__       ,	lowercase__       ,	lowercase__       ,	lowercase__       ):
               # Insert current vertex  into path as next transition
               a_       		=next_ver
               # Validate created path
               if util_hamilton_cycle(lowercase__       ,	lowercase__       ,	curr_ind + 1       ):
                    return True
               # Backtrack
               a_       		=-1
     return False






def  UpperCAmelCase_       (		lowercase__       ,	lowercase__ = 0       ):


     '''simple docstring'''







     a_       		=[-1] * (len(lowercase__       ) + 1)
     # initialize start and end of path with starting index
     a_       		=a_       		=start_index
     # evaluate and if we find answer return path either return empty array
     return path if util_hamilton_cycle(lowercase__       ,	lowercase__       ,	1       ) else []







'''simple docstring'''


from __future__ import annotations






def  UpperCAmelCase_       (		lowercase__       ):


     '''simple docstring'''







     a_       		=str(lowercase__       )
     return len(lowercase__       ) == 9 and set(lowercase__       ) == set("123456789"       )






def  UpperCAmelCase_       (		):


     '''simple docstring'''







     for base_num in range(9_9_9_9       ,	4_9_9_9       ,	-1       ):
          a_       		=1_0_0_0_0_2 * base_num
          if is_9_pandigital(lowercase__       ):
               return candidate

     for base_num in range(3_3_3       ,	9_9       ,	-1       ):
          a_       		=1_0_0_2_0_0_3 * base_num
          if is_9_pandigital(lowercase__       ):
               return candidate

     return None


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


