





_UpperCAmelCase										=					float('inf')



class 				_UpperCamelCase       :

       def __init__(		self:			Union[str, Any]       , _SCREAMING_SNAKE_CASE:			Dict		)							->			int:




              """simple docstring"""


              UpperCamelCase_ 							=	[0] * n
              UpperCamelCase_ 							=	[0] * n
              UpperCamelCase_ 							=	[0] * n
              UpperCamelCase_ 							=	[[] for _ in range(_SCREAMING_SNAKE_CASE		)]

       def lowercase			(		self:			Union[str, Any]       , _SCREAMING_SNAKE_CASE:			List[str]       , _SCREAMING_SNAKE_CASE:			Optional[Any]       , _SCREAMING_SNAKE_CASE:			str       , _SCREAMING_SNAKE_CASE:			int=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 lowercase			(		self:			int       , _SCREAMING_SNAKE_CASE:			List[str]       , _SCREAMING_SNAKE_CASE:			Tuple       , _SCREAMING_SNAKE_CASE:			List[Any]		)							->			Optional[Any]:




              """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]       , _SCREAMING_SNAKE_CASE       , min(_SCREAMING_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 lowercase			(		self:			int       , _SCREAMING_SNAKE_CASE:			int       , _SCREAMING_SNAKE_CASE:			str		)							->			Tuple:




              """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(_SCREAMING_SNAKE_CASE       , _SCREAMING_SNAKE_CASE       , _SCREAMING_SNAKE_CASE		)
                            while p:
                                   flow += p
                                   UpperCamelCase_ 							=	self.depth_first_search(_SCREAMING_SNAKE_CASE       , _SCREAMING_SNAKE_CASE       , _SCREAMING_SNAKE_CASE		)

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






"""simple docstring"""







from collections import namedtuple

A     =      namedtuple('from_to', 'from_ to')

A     =      {
    'millimeter': 'mm',
    'centimeter': 'cm',
    'meter': 'm',
    'kilometer': 'km',
    'inch': 'in',
    'inche': 'in',  # Trailing 's' has been stripped off
    'feet': 'ft',
    'foot': 'ft',
    'yard': 'yd',
    'mile': 'mi',
}

A     =      {
    'mm': from_to(0.001, 1_0_0_0),
    'cm': from_to(0.01, 1_0_0),
    'm': from_to(1, 1),
    'km': from_to(1_0_0_0, 0.001),
    'in': from_to(0.0254, 39.3701),
    'ft': from_to(0.3048, 3.2_8084),
    'yd': from_to(0.9144, 1.0_9361),
    'mi': from_to(1609.34, 0.0_0062_1371),
}

def 	lowerCAmelCase__      (  lowerCamelCase__					,   lowerCamelCase__					,   lowerCamelCase__      )			->				float:
							A    =       from_type.lower().rstrip('s'      )
							A    =       TYPE_CONVERSION.get(lowerCamelCase__					,   lowerCamelCase__      )
							A    =       to_type.lower().rstrip('s'      )
							A    =       TYPE_CONVERSION.get(lowerCamelCase__					,   lowerCamelCase__      )
							if new_from not in METRIC_CONVERSION:
														A    =       (
														    f"""Invalid 'from_type' value: {from_type!r}.\n"""
														    f"""Conversion abbreviations are: {', '.join(lowerCamelCase__      )}"""
														)
														raise ValueError(lowerCamelCase__      )
							if new_to not in METRIC_CONVERSION:
														A    =       (
														    f"""Invalid 'to_type' value: {to_type!r}.\n"""
														    f"""Conversion abbreviations are: {', '.join(lowerCamelCase__      )}"""
														)
														raise ValueError(lowerCamelCase__      )
							return value * METRIC_CONVERSION[new_from].from_ * METRIC_CONVERSION[new_to].to


if __name__ == "__main__":
							import doctest

							doctest.testmod()



