// Edmonds-Karp: Ford-Fulkerson with BFS to pick shortest augmenting paths.

class EdmondsKarp {
  int[][] maxflow(int[][] c, int s, int t) {
    int n = c.length;
    int[][] f      = new int[n][n];
    int[]   parent = new int[n];
    boolean done = false;
    while (!done) {
      int found = bfsResidual(c, f, s, t, parent);
      if (found == 0) {
        done = true;
      } else {
        // Bottleneck residual capacity along the path.
        int bottleneck = 2147483647;
        int v = t;
        while (v != s) {
          int u = parent[v];
          int r = c[u][v] - f[u][v];
          if (r < bottleneck) {
            bottleneck = r;
          };
          v = u;
        };
        v = t;
        while (v != s) {
          int u = parent[v];
          f[u][v] = f[u][v] + bottleneck;
          f[v][u] = f[v][u] - bottleneck;
          v = u;
        }
      }
    };
    return f;
  }

  // BFS in the residual graph; returns 1 iff t is reachable from s.
  // parent[v] receives the BFS-tree predecessor of v on a shortest
  // augmenting path from s.
  int bfsResidual(int[][] c, int[][] f, int s, int t, int[] parent) {
    int n = c.length;
    boolean[] seen = new boolean[n];
    int[] q = new int[n];
    int head = 0;
    int tail = 0;
    q[tail] = s;
    tail = tail + 1;
    seen[s] = true;
    parent[s] = s;
    while (head < tail) {
      int u = q[head];
      head = head + 1;
      if (u == t) {
        return 1;
      };
      int v = 0;
      while (v < n) {
        if (!seen[v] && c[u][v] - f[u][v] > 0) {
          seen[v] = true;
          parent[v] = u;
          q[tail] = v;
          tail = tail + 1;
        };
        v = v + 1;
      }
    };
    if (seen[t]) {
      return 1;
    };
    return 0;
  }
}