output_description: Print the maximum flow.
input_description: A flow network is given in the following format.
  
  $|V|\;|E|$  
  $u_0\;v_0\;c_0$  
  $u_1\;v_1\;c_1$  
  :  
  $u_{|E|-1}\;v_{|E|-1}\;c_{|E|-1}$  
    
  
  $|V|$, $|E|$ is the number of vertices and edges of the flow network
  respectively. The vertices in $G$ are named with the numbers 0, 1,...,
  $|V|-1$. The source is 0 and the sink is $|V|-1$.
  
  $u_i$, $v_i$, $c_i$ represent $i$-th edge of the flow network. A pair of $u_i$
  and $v_i$ denotes that there is an edge from $u_i$ to $v_i$ and $c_i$ is the
  capacity of $i$-th edge.
attempt: class Dinic:
      def __init__(self, n, g):
          self.n = n
          self.e = [[] for _ in range(n)]
          for i in range(n):
              for j, c in g[i]:
                  a = [j, c, None]
                  a[2] = b = [i, 0, a]
                  self.e[i].append(a)
                  self.e[j].append(b)
  
      def bfs(self, s, t):
          self.d = d = [None] * self.n
          d[s] = 0
          k = [s]
          e = self.e
          for i in k:
              for j, c, _ in e[i]:
                  if c and d[j] == None:
                      d[j] = d[i] + 1
                      k.append(j)
          return d[t] != None
  
      def dfs(self, v, t, f):
          if v == t:
              return f
          d = self.d
          for e in self.m[v]:
              w, c, r = e
              if c and d[v] < d[w]:
                  b = self.dfs(w, t, min(f, c))
                  if b:
                      e[1] -= b
                      r[1] += b
                      return b
          return 0
  
      def flow(self, s, t):
          l = 0
          x = 10**20
          while self.bfs(s, t):
              self.m = list(map(iter, self.e))
              f = x
              while f:
                  f = self.dfs(s, t, x)
                  l += f
          return l
  
  
  v, e = map(int, input().split())
  edge = [[] for _ in range(v)]
  for _ in range(e):
      uu, vv, c = map(int, input().split())
      edge[uu].append((vv, c))
  dinic = Dinic(v, edge)
  print(dinic.flow(0, v - 1))
  
problem_description: Maximum Flow
  
  A flow network is a directed graph which has a $source$ and a $sink$. In a
  flow network, each edge $(u, v)$ has a capacity $c(u, v)$. Each edge receives
  a flow, but the amount of flow on the edge can not exceed the corresponding
  capacity. Find the maximum flow from the $source$ to the $sink$.
samples: [{"input": "4 5\n    0 1 2\n    0 2 1\n    1 2 1\n    1 3 1\n    2 3 2", "output": "3"}]