


__snake_case     =		float('''inf''')



class 					__lowerCamelCase	:







       def __init__(	self:				Optional[int],A_:				Optional[int]			):






            '''simple docstring'''




            __UpperCamelCase				=	[0] * n
            __UpperCamelCase				=	[0] * n
            __UpperCamelCase				=	[0] * n
            __UpperCamelCase				=	[[] for _ in range(A_			)]







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






            '''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],A_,min(A_,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 						snake_case_					(	self:				List[str],A_:				Optional[int],A_:				Dict			):






            '''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(A_,A_,A_			)
                      while p:
                           flow += p
                           __UpperCamelCase				=	self.depth_first_search(A_,A_,A_			)

                      if not self.lvl[sink]:
                           break

            return flow
__snake_case     =		Dinic(1_0)
__snake_case     =		0
__snake_case     =		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))






import os

from apache_beam.io.filesystems import FileSystems
from apache_beam.pipeline import Pipeline

from .logging import get_logger


__snake_case     =		2 << 2_0  # 2mb
__snake_case     =		get_logger(__name__)



class 					__lowerCamelCase	(_a		):







       def 						snake_case_					(	self:				Optional[Any]			):






            '''simple docstring'''




            __UpperCamelCase				=	self._options.get_all_options().get('runner'			)
            return runner in [None, "DirectRunner", "PortableRunner"]






def 						_A						(						_lowercase			,       _lowercase			,       _lowercase=False				)			->				List[Any]:


     """simple docstring"""


     __UpperCamelCase				=	FileSystems
     if fs.exists(_lowercase				):
          if force_upload:
               logger.info(f'''Remote path already exist: {remote_file_path}. Overwriting it as force_upload=True.'''				)
          else:
               logger.info(f'''Remote path already exist: {remote_file_path}. Skipping it as force_upload=False.'''				)
               return
     with fs.create(_lowercase				) as remote_file:
          with open(_lowercase			,       'rb'				) as local_file:
               __UpperCamelCase				=	local_file.read(_lowercase				)
               while chunk:
                    remote_file.write(_lowercase				)
                    __UpperCamelCase				=	local_file.read(_lowercase				)






def 						_A						(						_lowercase			,       _lowercase			,       _lowercase=False				)			->				Optional[Any]:


     """simple docstring"""


     __UpperCamelCase				=	FileSystems
     if os.path.exists(_lowercase				):
          if force_download:
               logger.info(f'''Local path already exist: {remote_file_path}. Overwriting it as force_upload=True.'''				)
          else:
               logger.info(f'''Local path already exist: {remote_file_path}. Skipping it as force_upload=False.'''				)
               return
     with fs.open(_lowercase				) as remote_file:
          with open(_lowercase			,       'wb'				) as local_file:
               __UpperCamelCase				=	remote_file.read(_lowercase				)
               while chunk:
                    local_file.write(_lowercase				)
                    __UpperCamelCase				=	remote_file.read(_lowercase				)


