




a_      						=   float("inf")

class        _lowerCamelCase  :

      """simple docstring"""

      def __init__(   self    :       List[Any]       ,				snake_case    :       Union[str, Any] ):
          __UpperCamelCase     						=  [0] * n
          __UpperCamelCase     						=  [0] * n
          __UpperCamelCase     						=  [0] * n
          __UpperCamelCase     						=  [[] for _ in range(snake_case )]







      def 					snake_case		(   self    :       int       ,				snake_case    :       List[Any]       ,				snake_case    :       Optional[Any]       ,				snake_case    :       Any       ,				snake_case    :       Union[str, Any]=0 ):
          self.adj[a].append([b, len(self.adj[b] ), c, 0] )
          self.adj[b].append([a, len(self.adj[a] ) - 1, rcap, 0] )







      def 					snake_case		(   self    :       Any       ,				snake_case    :       List[Any]       ,				snake_case    :       Union[str, Any]       ,				snake_case    :       Optional[int] ):
          if vertex == sink or not flow:
              return flow

          for i in range(self.ptr[vertex]       ,				len(self.adj[vertex] ) ):
              __UpperCamelCase     						=  self.adj[vertex][i]
              if self.lvl[e[0]] == self.lvl[vertex] + 1:
                  __UpperCamelCase     						=  self.depth_first_search(e[0]       ,				snake_case       ,				min(snake_case       ,				e[2] - e[3] ) )
                  if p:
                      self.adj[vertex][i][3] += p
                      self.adj[e[0]][e[1]][3] -= p
                      return p
              __UpperCamelCase     						=  self.ptr[vertex] + 1
          return 0







      def 					snake_case		(   self    :       List[Any]       ,				snake_case    :       Union[str, Any]       ,				snake_case    :       List[str] ):
          __UpperCamelCase						,					__UpperCamelCase     						=  0, source
          for l in range(31 ):  # noqa: E741  l = 30 maybe faster for random data
              while True:
                  __UpperCamelCase						,					__UpperCamelCase     						=  [0] * len(self.q ), [0] * len(self.q )
                  __UpperCamelCase						,					__UpperCamelCase						,					__UpperCamelCase     						=  0, 1, 1
                  while qi < qe and not self.lvl[sink]:
                      __UpperCamelCase     						=  self.q[qi]
                      qi += 1
                      for e in self.adj[v]:
                          if not self.lvl[e[0]] and (e[2] - e[3]) >> (30 - l):
                              __UpperCamelCase     						=  e[0]
                              qe += 1
                              __UpperCamelCase     						=  self.lvl[v] + 1

                  __UpperCamelCase     						=  self.depth_first_search(snake_case       ,				snake_case       ,				snake_case )
                  while p:
                      flow += p
                      __UpperCamelCase     						=  self.depth_first_search(snake_case       ,				snake_case       ,				snake_case )

                  if not self.lvl[sink]:
                      break

          return flow
a_      						=   Dinic(10)
a_      						=   0
a_      						=   9
for vertex in range(1, 5):
 graph.add_edge(source, vertex, 1)
for vertex in range(5, 9):
 graph.add_edge(vertex, sink, 1)
for vertex in range(1, 5):
 graph.add_edge(vertex, vertex + 4, 1)

# Now we can know that is the maximum flow(source -> sink)
print(graph.max_flow(source, sink))












def     __SCREAMING_SNAKE_CASE      (     lowercase_					)				->		bool:

    """simple docstring"""


    if not isinstance(lowercase_    ,   lowercase_					):
        __UpperCamelCase     						=  F"Input value of [number={number}] must be an integer"
        raise TypeError(lowercase_					)
    if number < 0 or number % 2 == 1:
        return False
    __UpperCamelCase     						=  int(number**0.5					)
    return number == number_sqrt * (number_sqrt + 1)


if __name__ == "__main__":
 import doctest

 doctest.testmod()






