Dinic

template <typename T>
struct Dinic {
  struct Edge {
    int to;
    T cap;

    Edge(int to, T cap) : to(to), cap(cap) {
      void(0);
    }
  };

  int n;
  int s;
  int t;
  std::vector<int> lvl;
  std::vector<int> ptr;
  std::vector<Edge> edges;
  std::vector<std::vector<int>> g;

  Dinic(int n, int s, int t) : n(n), s(s), t(t), lvl(n), ptr(n), g(n) {
    assert(0 <= s && s < n);
    assert(0 <= t && t < n);
    assert(s != t);
  }

  void addEdge(int u, int v, T c, bool bidirectional = false) {
    g[u].push_back(edges.size());
    edges.emplace_back(v, c);
    g[v].push_back(edges.size());
    edges.emplace_back(u, bidirectional ? c : 0);
  }

  void initLevel() {
    std::fill(lvl.begin(), lvl.end(), -1);
    lvl[s] = 0;
    std::vector<int> que(1, s);
    for (int b = 0; b < int(que.size()); ++b) {
      for (int eid : g[que[b]]) {
        auto [to, cap] = edges[eid];
        if (cap > 0 && lvl[to] == -1) {
          lvl[to] = lvl[que[b]] + 1;
          que.push_back(to);
        }
      }
    }
  }

  T augment(int u, T lim) {
    if (u == t) {
      return lim;
    }
    for (int& i = ptr[u]; i < int(g[u].size()); ++i) {
      auto& e = edges[g[u][i]];
      if (e.cap > 0 && lvl[e.to] == lvl[u] + 1) {
        T flow = augment(e.to, std::min(lim, e.cap));
        if (flow > 0) {
          e.cap -= flow;
          edges[g[u][i] ^ 1].cap += flow;
          return flow;
        }
      }
    }
    return 0;
  }

  T work() {
    T res = 0;
    while (true) {
      initLevel();
      if (lvl[t] == -1) {
        break;
      }
      std::fill(ptr.begin(), ptr.end(), 0);
      while (true) {
        T flow = augment(s, std::numeric_limits<T>::max());
        if (flow == 0) {
          break;
        }
        res += flow;
      }
    }
    return res;
  }

  [[nodiscard]] std::vector<bool> getMinCut() const {
    std::vector<bool> res(n);
    for (int i = 0; i < n; ++i) {
      res[i] = (lvl[i] != -1);
    }
    return res;
  }
};