

lowerCamelCase_					  =   float('''inf''')







class 					__lowerCamelCase							:







      def __init__(	self				,    lowerCamelCase  )		->			Any:
        snake_case_					= [0] * n
        snake_case_					= [0] * n
        snake_case_					= [0] * n
        snake_case_					= [[] for _ in range(lowerCamelCase  )]







      def       lowerCAmelCase_       (	self				,    lowerCamelCase				,    lowerCamelCase				,    lowerCamelCase				,    lowerCamelCase=0  )		->			List[Any]:
        self.adj[a].append([b, len(self.adj[b]  ), c, 0]  )
        self.adj[b].append([a, len(self.adj[a]  ) - 1, rcap, 0]  )







      def       lowerCAmelCase_       (	self				,    lowerCamelCase				,    lowerCamelCase				,    lowerCamelCase  )		->			Union[str, Any]:
        if vertex == sink or not flow:
          return flow

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







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

            snake_case_					= self.depth_first_search(lowerCamelCase				,    lowerCamelCase				,    lowerCamelCase  )
            while p:
              flow += p
              snake_case_					= self.depth_first_search(lowerCamelCase				,    lowerCamelCase				,    lowerCamelCase  )

            if not self.lvl[sink]:
              break

        return flow
lowerCamelCase_					  =   Dinic(10)
lowerCamelCase_					  =   0
lowerCamelCase_					  =   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   UpperCamelCase(   lowercase_				)      ->							str:





  '''simple docstring'''





  return "".join(chr(ord(lowercase_				) + 32				) if """A""" <= char <= """Z""" else char for char in word				)


if __name__ == "__main__":
    from doctest import testmod

    testmod()