


'''simple docstring'''

_UpperCAmelCase					:			Dict				     =					float("""inf""")


class    a__					:







				"""simple docstring"""



				def __init__(self							,      __lowercase		):
										__lowerCAmelCase											=					[0] * n
										__lowerCAmelCase											=					[0] * n
										__lowerCAmelCase											=					[0] * n
										__lowerCAmelCase											=					[[] for _ in range(__lowercase		)]




				def        _snake_case	(self							,      __lowercase							,      __lowercase							,      __lowercase							,      __lowercase=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							,      __lowercase							,      __lowercase							,      __lowercase		):
										if vertex == sink or not flow:
																return flow

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




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

																						__lowerCAmelCase											=					self.depth_first_search(__lowercase							,      __lowercase							,      __lowercase		)
																						while p:
																												flow += p
																												__lowerCAmelCase											=					self.depth_first_search(__lowercase							,      __lowercase							,      __lowercase		)

																						if not self.lvl[sink]:
																												break

										return flow
_UpperCAmelCase					:			int				     =					Dinic(1_0)
_UpperCAmelCase					:			Dict				     =					0
_UpperCAmelCase					:			str				     =					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))





'''simple docstring'''

from __future__ import annotations

import random
from collections.abc import Iterable
from typing import Any, Generic, TypeVar

_UpperCAmelCase					:			Any				     =					TypeVar("""T""", bound=bool)


class    a__					(			Generic[T]   ):







				"""simple docstring"""



				def __init__(self							,      __lowercase		):
										__lowerCAmelCase											=					value
										__lowerCAmelCase											=					None
										__lowerCAmelCase											=					None




				@property
				def        _snake_case	(self		):
										return self._value




				@staticmethod
				def        _snake_case	(__lowercase							,      __lowercase		):
										if not roota:
																return roota

										if not roota:
																return roota

										if roota.value > roota.value:
																__lowerCAmelCase							,       __lowerCAmelCase											=					roota, roota

										if random.choice([True, False]		):
																__lowerCAmelCase							,       __lowerCAmelCase											=					roota.right, roota.left

										__lowerCAmelCase											=					RandomizedHeapNode.merge(roota.left							,      __lowercase		)

										return roota


class    a__					(			Generic[T]   ):







				"""simple docstring"""



				def __init__(self							,      __lowercase = ()		):
										__lowerCAmelCase											=					None

										if data:
																for item in data:
																						self.insert(__lowercase		)




				def        _snake_case	(self							,      __lowercase		):
										__lowerCAmelCase											=					RandomizedHeapNode.merge(self._root							,      RandomizedHeapNode(__lowercase		)		)




				def        _snake_case	(self		):
										__lowerCAmelCase											=					self.top()

										if self._root is None:
																return None

										__lowerCAmelCase											=					RandomizedHeapNode.merge(self._root.left							,      self._root.right		)

										return result




				def        _snake_case	(self		):
										if not self._root:
																raise IndexError('''Can\'t get top element for the empty heap.'''		)
										return self._root.value




				def        _snake_case	(self		):
										__lowerCAmelCase											=					None




				def        _snake_case	(self		):
										__lowerCAmelCase											=					[]
										while self:
																result.append(self.pop()		)

										return result




				def __bool__(self		):
										return self._root is not None


if __name__ == "__main__":
	import doctest

	doctest.testmod()

