


# 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  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      )->						Optional[int]:




      """simple docstring"""

      snake_case_ =   [False] * len(SCREAMING_SNAKE_CASE      )
      snake_case_ =   [-1] * len(SCREAMING_SNAKE_CASE      )

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

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

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

      return True


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




print(check_bipartite_dfs(graph))



from collections import namedtuple

UpperCAmelCase    =					namedtuple("""from_to""", """from_ to""")

UpperCAmelCase    =					{
    """cubicmeter""": from_to(1, 1),
    """litre""": from_to(0.001, 1000),
    """kilolitre""": from_to(1, 1),
    """gallon""": from_to(0.00_454, 264.172),
    """cubicyard""": from_to(0.76_455, 1.30_795),
    """cubicfoot""": from_to(0.028, 35.3_147),
    """cup""": from_to(0.000_236_588, 4_226.75),
}






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      )->						float:




      """simple docstring"""

      if from_type not in METRIC_CONVERSION:
            raise ValueError(
                f'''Invalid \'from_type\' value: {from_type!r}  Supported values are:\n'''
                + ''', '''.join(SCREAMING_SNAKE_CASE      )      )
      if to_type not in METRIC_CONVERSION:
            raise ValueError(
                f'''Invalid \'to_type\' value: {to_type!r}.  Supported values are:\n'''
                + ''', '''.join(SCREAMING_SNAKE_CASE      )      )
      return value * METRIC_CONVERSION[from_type].from_ * METRIC_CONVERSION[to_type].to


if __name__ == "__main__":
   import doctest

   doctest.testmod()