






__UpperCAmelCase      =				float("inf")
class 	a_:



     """simple docstring"""



     def __init__(		self					:	Optional[Any]  ,  lowerCAmelCase__					:	Tuple)							->	List[Any]:

      """simple docstring"""
      SCREAMING_SNAKE_CASE				    =		[0] * n
      SCREAMING_SNAKE_CASE				    =		[0] * n
      SCREAMING_SNAKE_CASE				    =		[0] * n
      SCREAMING_SNAKE_CASE				    =		[[] for _ in range(lowerCAmelCase__)]





     def     __UpperCamelCase						(		self					:	Dict  ,  lowerCAmelCase__					:	Dict  ,  lowerCAmelCase__					:	Optional[int]  ,  lowerCAmelCase__					:	Optional[Any]  ,  lowerCAmelCase__					:	Union[str, Any]=0)							->	Union[str, Any]:

      """simple docstring"""
      self.adj[a].append([b, len(self.adj[b]), c, 0])
      self.adj[b].append([a, len(self.adj[a]) - 1, rcap, 0])





     def     __UpperCamelCase						(		self					:	Dict  ,  lowerCAmelCase__					:	List[str]  ,  lowerCAmelCase__					:	Tuple  ,  lowerCAmelCase__					:	Dict)							->	Any:

      """simple docstring"""
      if vertex == sink or not flow:
       return flow

      for i in range(self.ptr[vertex]  ,  len(self.adj[vertex])):
       SCREAMING_SNAKE_CASE				    =		self.adj[vertex][i]
       if self.lvl[e[0]] == self.lvl[vertex] + 1:
        SCREAMING_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
       SCREAMING_SNAKE_CASE				    =		self.ptr[vertex] + 1
      return 0





     def     __UpperCamelCase						(		self					:	Optional[Any]  ,  lowerCAmelCase__					:	List[str]  ,  lowerCAmelCase__					:	int)							->	Union[str, Any]:

      """simple docstring"""
      SCREAMING_SNAKE_CASE    ,   SCREAMING_SNAKE_CASE				    =		0, source
      for l in range(3_1):  # noqa: E741  l = 30 maybe faster for random data
       while True:
        SCREAMING_SNAKE_CASE    ,   SCREAMING_SNAKE_CASE				    =		[0] * len(self.q), [0] * len(self.q)
        SCREAMING_SNAKE_CASE    ,   SCREAMING_SNAKE_CASE    ,   SCREAMING_SNAKE_CASE				    =		0, 1, 1
        while qi < qe and not self.lvl[sink]:
         SCREAMING_SNAKE_CASE				    =		self.q[qi]
         qi += 1
         for e in self.adj[v]:
          if not self.lvl[e[0]] and (e[2] - e[3]) >> (3_0 - l):
           SCREAMING_SNAKE_CASE				    =		e[0]
           qe += 1
           SCREAMING_SNAKE_CASE				    =		self.lvl[v] + 1

        SCREAMING_SNAKE_CASE				    =		self.depth_first_search(lowerCAmelCase__  ,  lowerCAmelCase__  ,  lowerCAmelCase__)
        while p:
         flow += p
         SCREAMING_SNAKE_CASE				    =		self.depth_first_search(lowerCAmelCase__  ,  lowerCAmelCase__  ,  lowerCAmelCase__)

        if not self.lvl[sink]:
         break

      return flow
__UpperCAmelCase      =				Dinic(1_0)
__UpperCAmelCase      =				0
__UpperCAmelCase      =				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 						A_					(						lowercase_	,  lowercase_			)				->List[Any]:







 """simple docstring"""

 SCREAMING_SNAKE_CASE				    =		1
 while b > 0:
  if b & 1:
   res *= a

  a *= a
  b >>= 1

 return res





def 						A_					(						lowercase_	,  lowercase_	,  lowercase_			)				->Any:







 """simple docstring"""

 SCREAMING_SNAKE_CASE				    =		1
 while b > 0:
  if b & 1:
   SCREAMING_SNAKE_CASE				    =		((res % c) * (a % c)) % c

  a *= a
  b >>= 1

 return res




