





def      UpperCAmelCase_    (    _UpperCAmelCase							:Optional[Any]  ,						_UpperCAmelCase							:Union[str, Any]  ,						_UpperCAmelCase							:str  ,						_UpperCAmelCase							:Union[str, Any]				)	->				Any:
     '''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_    (    _UpperCAmelCase							:Any  ,						_UpperCAmelCase							:str  ,						_UpperCAmelCase							:Optional[int]				)	->				Any:
     '''simple docstring'''


     if curr_ind == len(_A				):
          # 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(_A				)				):
          if valid_connection(_A  ,						_A  ,						_A  ,						_A				):
               # Insert current vertex  into path as next transition
               A_          =       next_ver
               # Validate created path
               if util_hamilton_cycle(_A  ,						_A  ,						curr_ind + 1				):
                    return True
               # Backtrack
               A_          =       -1
     return False


def      UpperCAmelCase_    (    _UpperCAmelCase							:Tuple  ,						_UpperCAmelCase							:Dict = 0				)	->				Any:
     '''simple docstring'''


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







'''simple docstring'''







def       lowercase					(_A       ):







       """simple docstring"""







       if len(_A       ) <= 1:
              return [tuple(_A       )]

       _lowerCAmelCase     :				List[str]       =							[]

       def generate(_A ,    _A       ):
              _lowerCAmelCase     :				Any       =							[0] * n
              res.append(tuple(_A       )       )

              _lowerCAmelCase     :				Any       =							0
              while i < n:
                     if c[i] < i:
                            if i % 2 == 0:
                                   _lowerCAmelCase      ,  _lowerCAmelCase     :				Tuple       =							arr[i], arr[0]
                            else:
                                   _lowerCAmelCase      ,  _lowerCAmelCase     :				List[str]       =							arr[i], arr[c[i]]
                            res.append(tuple(_A       )       )
                            c[i] += 1
                            _lowerCAmelCase     :				Optional[int]       =							0
                     else:
                            _lowerCAmelCase     :				Any       =							0
                            i += 1

       generate(len(_A       ) ,    _A       )
       return res


if __name__ == "__main__":
       lowerCAmelCase     :  int											=    input("""Enter numbers separated by a comma:\n""").strip()
       lowerCAmelCase     :  Optional[int]											=    [int(item) for item in user_input.split(""",""")]
       print(heaps(arr))

