__lowerCAmelCase    :  Optional[Any]										= float('inf')
class 				lowerCamelCase			:






      def __init__(      self  ,		__lowerCamelCase						)     ->				int:


          '''simple docstring'''







          snake_case:						int         =   [0] * n
          snake_case:						List[str]         =   [0] * n
          snake_case:						Union[str, Any]         =   [0] * n
          snake_case:						Union[str, Any]         =   [[] for _ in range(__lowerCamelCase						)]






      def 			lowerCAmelCase_   (      self  ,		__lowerCamelCase  ,		__lowerCamelCase  ,		__lowerCamelCase  ,		__lowerCamelCase=0						)     ->				str:


          '''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 			lowerCAmelCase_   (      self  ,		__lowerCamelCase  ,		__lowerCamelCase  ,		__lowerCamelCase						)     ->				Optional[Any]:


          '''simple docstring'''







          if vertex == sink or not flow:
              return flow

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






      def 			lowerCAmelCase_   (      self  ,		__lowerCamelCase  ,		__lowerCamelCase						)     ->				Union[str, Any]:


          '''simple docstring'''







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

                  snake_case:						Optional[Any]         =   self.depth_first_search(__lowerCamelCase  ,		__lowerCamelCase  ,		__lowerCamelCase						)
                  while p:
                      flow += p
                      snake_case:						List[str]         =   self.depth_first_search(__lowerCamelCase  ,		__lowerCamelCase  ,		__lowerCamelCase						)

                  if not self.lvl[sink]:
                      break

          return flow
__lowerCAmelCase    :  Any										= Dinic(10)
__lowerCAmelCase    :  Dict										= 0
__lowerCAmelCase    :  Union[str, Any]										= 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_					(_lowerCAmelCase  :   int       )->				str:
    if not isinstance(_lowerCAmelCase			,	_lowerCAmelCase       ):
        snake_case:						Optional[Any]         =   (
            """operation can not be conducted on a object of type """
            F"{type(_lowerCAmelCase       ).__name__}"
        )
        raise TypeError(_lowerCAmelCase       )
    snake_case:						List[Any]         =   """"""
    for _ in range(0			,	32       ):
        bit_string += str(number % 2       )
        snake_case:						Any         =   number >> 1
    return bit_string

def   a_					(_lowerCAmelCase  :   int       )->				str:
    if number < 0:
        raise ValueError("""the value of input must be positive"""       )
    elif isinstance(_lowerCAmelCase			,	_lowerCAmelCase       ):
        raise TypeError("""Input value must be a 'int' type"""       )
    elif isinstance(_lowerCAmelCase			,	_lowerCAmelCase       ):
        raise TypeError("""'<' not supported between instances of 'str' and 'int'"""       )
    snake_case:						Optional[Any]         =   0
    # iterator over [1 to 32],since we are dealing with 32 bit integer
    for _ in range(1			,	33       ):
        # left shift the bits by unity
        snake_case:						Dict         =   result << 1
        # get the end bit
        snake_case:						Union[str, Any]         =   number % 2
        # right shift the bits by unity
        snake_case:						Union[str, Any]         =   number >> 1
        # add that bit to our ans
        snake_case:						Tuple         =   result | end_bit
    return get_reverse_bit_string(_lowerCAmelCase       )


if __name__ == "__main__":
    import doctest

    doctest.testmod()


