





# A Bipartite Graph is a graph whose vertices can be divided into two independent sets,
# U and V such that every edge (u, v) either connects a vertex from U to V or a vertex
# from V to U. In other words, for every edge (u, v), either u belongs to U and v to V,
# or u belongs to V and v to U. We can also say that there is no edge that connects
# vertices of same set.


def     SCREAMING_SNAKE_CASE			(      lowerCAmelCase					):
       _UpperCamelCase              =						[False] * len(lowerCAmelCase					)
       _UpperCamelCase              =						[-1] * len(lowerCAmelCase					)

       def dfs(lowerCAmelCase    ,       lowerCAmelCase					):
              _UpperCamelCase              =						True
              _UpperCamelCase              =						c
              for u in graph[v]:
                     if not visited[u]:
                            dfs(lowerCAmelCase    ,       1 - c					)

       for i in range(len(lowerCAmelCase					)					):
              if not visited[i]:
                     dfs(lowerCAmelCase    ,       0					)

       for i in range(len(lowerCAmelCase					)					):
              for j in graph[i]:
                     if color[i] == color[j]:
                            return False

       return True


# Adjacency list of graph
lowercase    : Optional[Any]    	=  {0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2], 4: []}

print(check_bipartite_dfs(graph))













def     SCREAMING_SNAKE_CASE			(      lowerCAmelCase					):
       _UpperCamelCase              =						[]
       if len(lowerCAmelCase					) == 1:
              return [nums.copy()]
       for _ in range(len(lowerCAmelCase					)					):
              _UpperCamelCase              =						nums.pop(0					)
              _UpperCamelCase              =						permute(lowerCAmelCase					)
              for perm in permutations:
                     perm.append(lowerCAmelCase					)
              result.extend(lowerCAmelCase					)
              nums.append(lowerCAmelCase					)
       return result


def     SCREAMING_SNAKE_CASE			(      lowerCAmelCase					):

       def backtrack(lowerCAmelCase					):
              if start == len(lowerCAmelCase					) - 1:
                     output.append(nums[:]					)
              else:
                     for i in range(lowerCAmelCase    ,       len(lowerCAmelCase					)					):
                            _UpperCamelCase       ,		_UpperCamelCase              =						nums[i], nums[start]
                            backtrack(start + 1					)
                            _UpperCamelCase       ,		_UpperCamelCase              =						nums[i], nums[start]  # backtrack

       _UpperCamelCase              =						[]
       backtrack(0					)
       return output


if __name__ == "__main__":
       import doctest

       # use res to print the data in permute2 function
       lowercase    : Optional[Any]    	=  permutea([1, 2, 3])
       print(res)
       doctest.testmod()






