




UpperCAmelCase_   							=      float('inf')





class        lowerCamelCase__:
      def __init__(							self:					Union[str, Any]       ,			UpperCamelCase_:					str  ):
             __lowerCamelCase  =		[0] * n
             __lowerCamelCase  =		[0] * n
             __lowerCamelCase  =		[0] * n
             __lowerCamelCase  =		[[] for _ in range(UpperCamelCase_  )]
      def      lowerCAmelCase__		(							self:					Union[str, Any]       ,			UpperCamelCase_:					List[str]       ,			UpperCamelCase_:					List[str]       ,			UpperCamelCase_:					Optional[int]       ,			UpperCamelCase_:					str=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      lowerCAmelCase__		(							self:					List[Any]       ,			UpperCamelCase_:					Any       ,			UpperCamelCase_:					List[Any]       ,			UpperCamelCase_:					Dict  ):
             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]       ,			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
                    __lowerCamelCase  =		self.ptr[vertex] + 1
             return 0




      def      lowerCAmelCase__		(							self:					Optional[Any]       ,			UpperCamelCase_:					Dict       ,			UpperCamelCase_:					Any  ):
             __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(UpperCamelCase_       ,			UpperCamelCase_       ,			UpperCamelCase_  )
                           while p:
                                  flow += p
                                  __lowerCamelCase  =		self.depth_first_search(UpperCamelCase_       ,			UpperCamelCase_       ,			UpperCamelCase_  )

                           if not self.lvl[sink]:
                                  break

             return flow
UpperCAmelCase_   							=      Dinic(10)
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))







from functools import partial
from typing import Any, Callable, Dict, List, Type, TypeVar, Union, overload

import torch
import torch.nn as nn
import torch.types




def    lowerCamelCase__			(		A__			:   torch.Tensor    ,     A__			:   torch.Tensor    ,     A__			:   bool      ):





       '''simple docstring'''



       if not inplace:
              __lowerCamelCase  =		ma + ma
       else:
              ma += ma

       return ma




def    lowerCamelCase__			(		A__			:   torch.Tensor    ,     A__			:   List[int]      ):





       '''simple docstring'''



       __lowerCamelCase  =		-1 * len(A__      )
       __lowerCamelCase  =		list(range(len(tensor.shape[:zero_index]      )      )      )
       return tensor.permute(first_inds + [zero_index + i for i in inds]      )




def    lowerCamelCase__			(		A__			:   torch.Tensor    ,     A__			:   int      ):





       '''simple docstring'''



       return t.reshape(t.shape[:-no_dims] + (-1,)      )




def    lowerCamelCase__			(		A__			:   torch.Tensor    ,     A__			:   torch.Tensor    ,     A__			:   int    ,     A__			:   float = 1E-4      ):





       '''simple docstring'''



       __lowerCamelCase  =		mask.expand(*value.shape      )
       return torch.sum(mask * value    ,     dim=A__      ) / (eps + torch.sum(A__    ,     dim=A__      ))




def    lowerCamelCase__			(		A__			:   torch.Tensor    ,     A__			:   torch.types.Number = 2.3_125    ,     A__			:   torch.types.Number = 21.6_875    ,     A__			:   int = 64      ):





       '''simple docstring'''



       __lowerCamelCase  =		torch.linspace(A__    ,     A__    ,     no_bins - 1    ,     device=pts.device      )
       __lowerCamelCase  =		torch.sqrt(torch.sum((pts.unsqueeze(-2      ) - pts.unsqueeze(-3      )) ** 2    ,     dim=-1      )      )
       return torch.bucketize(A__    ,     A__      )




def    lowerCamelCase__			(		A__			:   Callable[[list], Any]    ,     A__			:   List[dict]      ):





       '''simple docstring'''



       __lowerCamelCase  =		dicts[0]
       __lowerCamelCase  =		{}
       for k, v in first.items():
              __lowerCamelCase  =		[d[k] for d in dicts]
              if isinstance(A__    ,     A__      ):
                     __lowerCamelCase  =		dict_multimap(A__    ,     A__      )
              else:
                     __lowerCamelCase  =		fn(A__      )

       return new_dict




def    lowerCamelCase__			(		A__			:   torch.Tensor    ,     A__			:   torch.Tensor      ):





       '''simple docstring'''



       __lowerCamelCase  =		v_bins.view(((1,) * len(x.shape      )) + (len(A__      ),)      )
       __lowerCamelCase  =		x[..., None] - reshaped_bins
       __lowerCamelCase  =		torch.argmin(torch.abs(A__      )    ,     dim=-1      )
       return nn.functional.one_hot(A__    ,     num_classes=len(A__      )      ).float()




def    lowerCamelCase__			(		A__			:   torch.Tensor    ,     A__			:   torch.Tensor    ,     A__			:   int = 0    ,     A__			:   int = 0      ):





       '''simple docstring'''



       __lowerCamelCase  =		[]
       for i, s in enumerate(data.shape[:no_batch_dims]      ):
              __lowerCamelCase  =		torch.arange(A__      )
              __lowerCamelCase  =		r.view(*(*((1,) * i), -1, *((1,) * (len(inds.shape      ) - i - 1)))      )
              ranges.append(A__      )

       __lowerCamelCase  =		[slice(A__      ) for _ in range(len(data.shape      ) - no_batch_dims      )]
       __lowerCamelCase  =		inds
       ranges.extend(A__      )
       # Matt note: Editing this to get around the behaviour of using a list as an array index changing
       # in recent Numpy versions
       return data[tuple(A__      )]


UpperCAmelCase_   							=      TypeVar('T')




def    lowerCamelCase__			(		A__			:   Callable[[T], Any]    ,     A__			:   Dict[Any, Union[dict, list, tuple, T]]    ,     A__			:   Type[T]      ):





       '''simple docstring'''



       __lowerCamelCase  =		{}
       for k, v in dic.items():
              if isinstance(A__    ,     A__      ):
                     __lowerCamelCase  =		dict_map(A__    ,     A__    ,     A__      )
              else:
                     __lowerCamelCase  =		tree_map(A__    ,     A__    ,     A__      )

       return new_dict




@overload
def    lowerCamelCase__			(		A__			:   Callable[[T], Any]    ,     A__			:   T    ,     A__			:   Type[T]      ):





       '''simple docstring'''



       ...




@overload
def    lowerCamelCase__			(		A__			:   Callable[[T], Any]    ,     A__			:   dict    ,     A__			:   Type[T]      ):





       '''simple docstring'''



       ...




@overload
def    lowerCamelCase__			(		A__			:   Callable[[T], Any]    ,     A__			:   list    ,     A__			:   Type[T]      ):





       '''simple docstring'''



       ...




@overload
def    lowerCamelCase__			(		A__			:   Callable[[T], Any]    ,     A__			:   tuple    ,     A__			:   Type[T]      ):





       '''simple docstring'''



       ...




def    lowerCamelCase__			(		A__			:   Dict    ,     A__			:   List[str]    ,     A__			:   List[str]      ):





       '''simple docstring'''



       if isinstance(A__    ,     A__      ):
              return dict_map(A__    ,     A__    ,     A__      )
       elif isinstance(A__    ,     A__      ):
              return [tree_map(A__    ,     A__    ,     A__      ) for x in tree]
       elif isinstance(A__    ,     A__      ):
              return tuple(tree_map(A__    ,     A__    ,     A__      ) for x in tree      )
       elif isinstance(A__    ,     A__      ):
              return fn(A__      )
       else:
              print(type(A__      )      )
              raise ValueError("""Not supported"""      )




UpperCAmelCase_   							=      partial(tree_map, leaf_type=torch.Tensor)

