






_a   			=						float('''inf''')





class __lowerCamelCase				:





	"""simple docstring"""






	def __init__(							self ,					UpperCAmelCase					):
							"""simple docstring"""







							_UpperCAmelCase             =    [0] * n
							_UpperCAmelCase             =    [0] * n
							_UpperCAmelCase             =    [0] * n
							_UpperCAmelCase             =    [[] for _ in range(UpperCAmelCase					)]

	def  UpperCamelCase					(							self ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase=0					):
							"""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 ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase					):
							"""simple docstring"""







							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] ,					UpperCAmelCase ,					min(UpperCAmelCase ,					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  UpperCamelCase					(							self ,					UpperCAmelCase ,					UpperCAmelCase					):
							"""simple docstring"""







							_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(UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase					)
																			while p:
																									flow += p
																									_UpperCAmelCase             =    self.depth_first_search(UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase					)

																			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))








from typing import Any





class __lowerCamelCase				:





	"""simple docstring"""






	def __init__(							self					):
							"""simple docstring"""







							_UpperCAmelCase             =    []
							_UpperCAmelCase             =    0

	def __str__(							self					):
							"""simple docstring"""







							_UpperCAmelCase             =    '<' + str(self.stack					)[1:-1] + '>'
							return printed

	def  UpperCamelCase					(							self ,					UpperCAmelCase					):
							"""simple docstring"""







							self.stack.append(UpperCAmelCase					)
							_UpperCAmelCase             =    self.length + 1

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							self.rotate(1					)
							_UpperCAmelCase             =    self.stack[self.length - 1]
							_UpperCAmelCase             =    self.stack[:-1]
							self.rotate(self.length - 1					)
							_UpperCAmelCase             =    self.length - 1
							return dequeued

	def  UpperCamelCase					(							self ,					UpperCAmelCase					):
							"""simple docstring"""







							for _ in range(UpperCAmelCase					):
													_UpperCAmelCase             =    self.stack[0]
													_UpperCAmelCase             =    self.stack[1:]
													self.put(UpperCAmelCase					)
													_UpperCAmelCase             =    self.length - 1

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							_UpperCAmelCase             =    self.get()
							self.put(UpperCAmelCase					)
							self.rotate(self.length - 1					)
							return front

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							return self.length
