text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Finds the centroid of each component of a tree,
//   and recursively splits the component at that vertex
// Can be used to create a centroid tree, which has depth O(log V)
// Function Arguments:
//   G: a generic forest structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the forest
//   f(G, excl, c, p): a function to call on each centroid of its
//     component where G is a reference to the graph, excl is a reference to
//     an array of bools that indicates whether a vertex has been previously
//     used as a centroid, c is the current centroid (excl[c] is false),
//     and p is its parent in the centorid tree
// Return Value: a vector of integers representing the parent of each vertex
//   in the centroid tree, or -1 if it is a root
// In practice, has a moderate constant
// Time Complexity: O(V log V)
// Memory Complexity: O(V)
// Tested:
//   https://codeforces.com/contest/321/problem/C
//   https://codeforces.com/contest/161/problem/D
template <class Forest, class F>
vector<int> centroidDecomposition(const Forest &G, F f) {
  int V = G.size(); vector<int> size(V), par(V, -1);
  vector<bool> excl(V, false);
  function<int(int, int)> getSize = [&] (int v, int prev) {
    size[v] = 1;
    for (int w : G[v]) if (w != prev && !excl[w]) size[v] += getSize(w, v);
    return size[v];
  };
  function<int(int, int, int)> dfs = [&] (int v, int prev, int compSize) {
    for (int w : G[v]) if (w != prev && !excl[w] && size[w] > compSize / 2)
      return dfs(w, v, compSize);
    return v;
  };
  vector<pair<int, int>> q(V); for (int s = 0; s < V; s++) if (par[s] == -1) {
    int front = 0, back = 0; q[back++] = make_pair(s, -1);
    while (front < back) {
      int v = q[front].first, c = dfs(v, -1, getSize(v, -1));
      par[c] = q[front++].second; f(G, excl, c, par[c]); excl[c] = true;
      for (int w : G[c]) if (!excl[w]) q[back++] = make_pair(w, c);
    }
  }
  return par;
}


text:
#pragma once
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;

// Computes the global minimum cut for a weighted graph
// A cut is a partition of the vertices into two nonempty subsets
// A crossing edge is an edge with endpoints in both subsets
// The cost of a cut is the sum of the weights of the crossing edges
// Vertices are 0-indexed
// Template Arguments:
//   T: the type of the weight of the edges in the graph
// Constructor Arguments:
//   V: the number of vertices in the graph
//   INF: a value for infinity
// Fields:
//   cut: vector of booleans representing which side of the cut each vertex
//     is on
//   cutWeight: the weight of the global minimum cut
// Functions:
//   addEdge(v, w, weight): adds an undirected edge between vertices v
//     and w, with a weight of weight
//   globalMinCut(): returns the global minimum cut of the current graph
//     and updates the cut array
// In practice, has a very small constant
// Time Complexity:
//   constructor: O(V)
//   addEdge: O(1)
//   globalMinCut: O(V (V + E) log V)
// Memory Complexity: O(V^2 + E)
// Tested:
//   https://dmoj.ca/problem/checkercut
//   https://hackerrank.com/contests/w37/challenges/two-efficient-teams/problem
template <class T> struct StoerWagnerGlobalMinCut {
  struct Edge {
    int to, rev; T weight;
    Edge(int to, int rev,  T weight) : to(to), rev(rev), weight(weight) {}
  };
  struct Node {
    T w; int v; Node(T w, int v) : w(w), v(v) {}
    bool operator < (const Node &o) const { return w < o.w; }
  };
  int V; vector<vector<Edge>> G; vector<bool> cut; T cutWeight, INF;
  void addEdge(int v, int w, T weight) {
    if (v == w) return;
    G[v].emplace_back(w, int(G[w].size()), weight);
    G[w].emplace_back(v, int(G[v].size()) - 1, weight);
  }
  StoerWagnerGlobalMinCut(int V, T INF = numeric_limits<T>::max())
      : V(V), G(V), cut(V, false), cutWeight(INF), INF(INF) {}
  T globalMinCut() {
    vector<vector<Edge>> H = G; fill(cut.begin(), cut.end(), false);
    cutWeight = INF; vector<int> par(V); iota(par.begin(), par.end(), 0);
    for (int phase = V - 1; phase > 0; phase--) {
      vector<T> W(V, T()); __gnu_pbds::priority_queue<Node> PQ;
      vector<typename decltype(PQ)::point_iterator> ptr(V, PQ.end());
      for (int v = 1; v < V; v++) if (par[v] == v)
        ptr[v] = PQ.push(Node(W[v], v));
      for (auto &&e : H[0]) if (ptr[e.to] != PQ.end())
        PQ.modify(ptr[e.to], Node(W[e.to] += e.weight, e.to));
      for (int i = 0, v, last = 0; i < phase; i++, last = v) {
        T w = PQ.top().w; v = PQ.top().v; PQ.pop(); ptr[v] = PQ.end();
        if (i == phase - 1) {
          if (cutWeight > w) {
            cutWeight = w; for (int x = 0; x < V; x++) cut[x] = par[x] == v;
          }
          fill(W.begin(), W.end(), T());
          for (auto &&e : H[v]) W[e.to] += e.weight;
          for (auto &&e : H[last]) {
            e.weight += W[e.to]; H[e.to][e.rev].weight += W[e.to];
            W[e.to] = T();
          }
          for (auto &&e : H[v]) if (W[e.to] != T()) {
            H[e.to][e.rev].to = last; H[e.to][e.rev].rev = H[last].size();
            H[last].emplace_back(e.to, e.rev, e.weight);
          }
          H[v].clear();
          for (int x = 0; x < V; x++) if (par[x] == v) par[x] = last;
        } else {
          for (auto &&e : H[v]) if (ptr[e.to] != PQ.end())
            PQ.modify(ptr[e.to], Node(W[e.to] += e.weight, e.to));
        }
      }
    }
    return cutWeight;
  }
};

repo_name: wesley-a-leung/Resources

mime_type: text/x-c++


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Computes the global minimum cut for a weighted graph
// A cut is a partition of the vertices into two nonempty subsets
// A crossing edge is an edge with endpoints in both subsets
// The cost of a cut is the sum of the weights of the crossing edges
// Vertices are 0-indexed
// Template Arguments:
//   T: the type of the weight of the edges in the graph
// Constructor Arguments:
//   V: the number of vertices in the graph
//   INF: a value for infinity
// Fields:
//   cut: vector of booleans representing which side of the cut each vertex
//     is on
//   cutWeight: the weight of the global minimum cut
// Functions:
//   addEdge(v, w, weight): adds an undirected edge between vertices v
//     and w, with a weight of weight
//   globalMinCut(): returns the global minimum cut of the current graph
//     and updates the cut array
// In practice, has a very small constant
// Time Complexity:
//   constructor: O(V^2)
//   addEdge: O(1)
//   globalMinCut: O(V^3)
// Memory Complexity: O(V^2)
// Tested:
//   https://dmoj.ca/problem/checkercut
//   https://hackerrank.com/contests/w37/challenges/two-efficient-teams/problem
template <class T> struct ClassicalStoerWagnerGlobalMinCut {
  int V; vector<vector<T>> G; vector<bool> cut; T cutWeight, INF;
  void addEdge(int v, int w, T weight) {
    if (v == w) return;
    G[v][w] += weight; G[w][v] += weight;
  }
  ClassicalStoerWagnerGlobalMinCut(int V, T INF = numeric_limits<T>::max())
      : V(V), G(V, vector<T>(V, T())), cut(V, false),
        cutWeight(INF), INF(INF) {}
  T globalMinCut() {
    vector<vector<T>> H = G; fill(cut.begin(), cut.end(), false);
    cutWeight = INF; vector<int> par(V); iota(par.begin(), par.end(), 0);
    for (int phase = V - 1; phase > 0; phase--) {
      vector<T> W = H[0]; vector<bool> vis(V, true);
      for (int v = 0; v < V; v++) vis[v] = par[v] != v;
      for (int i = 0, v, last = 0; i < phase; i++, last = v) {
        v = -1; for (int w = 1; w < V; w++)
          if (!vis[w] && (v == -1 || W[v] < W[w])) v = w;
        if (i == phase - 1) {
          if (cutWeight > W[v]) {
            cutWeight = W[v]; for (int w = 0; w < V; w++) cut[w] = par[w] == v;
          }
          for (int w = 0; w < V; w++) {
            H[last][w] += H[v][w]; H[w][last] += H[v][w];
            if (par[w] == v) par[w] = last;
          }
        } else {
          vis[v] = true; for (int w = 0; w < V; w++) W[w] += H[v][w];
        }
      }
    }
    return cutWeight;
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Computes the strongly connected components of a directed graph using
//   Tarjan's algorithm
// Vertices are 0-indexed
// Constructor Arguments:
//   G: a generic directed graph structure which can be weighted or unweighted,
//       though weights do not change the components
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints for an unweighted graph, or a list of
//         pair<int, T> for a weighted graph with weights of type T)
//       size() const: returns the number of vertices in the graph
//   condensationEdges: a reference to a vector of pairs that will store the
//     edges in the condensation graph when all vertices in an scc are
//     condensed into a single vertex (with an index equal to its scc id),
//     and it is guaranteed that this list of edges is sorted by the first
//     element in the pair in non decreasing order
// Fields:
//   id: a vector of the index of the scc each vertex is part of
//   components: a vector of vectors containing the vertices in each scc and
//     is sorted in reverse topological order
// In practice, has a moderate constant, faster than Kosaraju
// Time Complexity:
//   constructor: O(V + E)
// Memory Complexity: O(V)
// Tested:
//   Stress Tested
//   https://judge.yosupo.jp/problem/scc
//   https://dmoj.ca/problem/acc2p2
//   https://open.kattis.com/problems/watchyourstep
struct SCC {
  int ind, top; vector<int> id, low, stk; vector<vector<int>> components;
  int getTo(int e) { return e; }
  template <class T> int getTo(const pair<int, T> &e) { return e.first; }
  template <class Digraph> void dfs(const Digraph &G, int v) {
    id[stk[top++] = v] = -1; int mn = low[v] = ind++; for (auto &&e : G[v]) {
      int w = getTo(e); if (id[w] == -2) dfs(G, w);
      mn = min(mn, low[w]);
    }
    if (mn < low[v]) { low[v] = mn; return; }
    int w; components.emplace_back(); do {
      id[w = stk[--top]] = components.size() - 1; low[w] = INT_MAX;
      components.back().push_back(w);
    } while (w != v);
  }
  template <class Digraph> SCC(const Digraph &G)
      : ind(0), top(0), id(G.size(), -2), low(G.size()), stk(G.size()) {
    for (int v = 0; v < int(G.size()); v++) if (id[v] == -2) dfs(G, v);
  }
  template <class Digraph>
  SCC(const Digraph &G, vector<pair<int, int>> &condensationEdges) : SCC(G) {
    vector<int> last(components.size(), -1);
    for (auto &&comp : components) for (int v : comp) for (auto &&e : G[v]) {
      int w = getTo(e); if (id[v] != id[w] && last[id[w]] != id[v])
        condensationEdges.emplace_back(last[id[w]] = id[v], id[w]);
    }
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../datastructures/unionfind/UnionFind.h"
using namespace std;

// Support online queries for the number of bridges in a graph, after edges
//   have been added
// Constructor Arguments:
//   V: the number of vertices in the graph
// Fields:
//   bridgeCnt: the current number of bridges in the graph
//   uf1: a UnionFind data structure representing the 1-edge connected
//     components
//   uf2: a UnionFind data structure representing the 2-edge connected
//     components
// Functions:
//   addEdge(v, w): adds an edge between vertices v and w
// Time Complexity:
//   constructor: O(V)
//   addEdge: O(log V) amortized
// Memory Complexity: O(V)
// Tested:
//   https://codeforces.com/gym/100551/problem/B
struct IncrementalBridges {
  UnionFind uf1, uf2; vector<int> par, mn, vis; int stamp, bridgeCnt;
  IncrementalBridges(int V)
      : uf1(V), uf2(V), par(V, -1), mn(V), vis(V, -1),
        stamp(-1), bridgeCnt(0) {
    iota(mn.begin(), mn.end(), 0);
  }
  void addEdge(int v, int w) {
    if (uf2.connected(v, w)) return;
    if (uf1.connected(v, w)) {
      stamp++; int lca = -1; for (int x = v, y = w;; swap(x, y)) if (x != -1) {
        if (vis[x = mn[uf2.find(x)]] == stamp) { lca = x; break; }
        vis[x] = stamp; x = par[x];
      }
      for (int h = 0; h < 2; h++, swap(v, w))
        for (v = mn[uf2.find(v)]; v != lca;) {
          int p = mn[uf2.find(par[v])], pp = par[p]; uf2.join(v, p);
          par[v = mn[uf2.find(v)] = p] = pp; bridgeCnt--;
        }
    } else {
      if (uf1.getSize(v) < uf1.getSize(w)) swap(v, w);
      for (int p = -1, last = v, x = w; x != -1; last = x, x = p) {
        p = par[x = mn[uf2.find(x)]]; par[x] = last;
      }
      bridgeCnt++; uf1.join(v, w);
    }
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Decomposes an undirected graph into 2-edge connected components and
//   identifies bridges
// Vertices are 0-indexed
// Constructor Arguments:
//   G: a generic undirected graph structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the graph
// Fields:
//   id: a vector of the index of the 2-edge connected component each vertex
//     is part of
//   components: a vector of vectors containing the vertices in each 2-edge
//     connected component
//   bridges: a vector of pairs that stores the bridges in the graph
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O(V + E)
// Memory Complexity: O(V)
// Tested:
//   Stress Tested
//   https://judge.yosupo.jp/problem/two_edge_connected_components
struct Bridges {
  int ind, top; vector<int> id, low, pre, stk; vector<vector<int>> components;
  vector<pair<int, int>> bridges;
  void makeComponent(int v) {
    int w; components.emplace_back(); do {
      id[w = stk[--top]] = components.size() - 1;
      components.back().push_back(w);
    } while (w != v);
  }
  template <class Graph> void dfs(const Graph &G, int v, int prev) {
    id[stk[top++] = v] = -1; low[v] = pre[v] = ind++; bool parEdge = false;
    for (int w : G[v]) {
      if (w == prev && !parEdge) parEdge = true;
      else if (id[w] == -2) {
        dfs(G, w, v); low[v] = min(low[v], low[w]);
        if (low[w] == pre[w]) { bridges.emplace_back(v, w); makeComponent(w); }
      } else low[v] = min(low[v], pre[w]);
    }
  }
  template <class Graph> Bridges(const Graph &G)
      : ind(0), top(0), id(G.size(), -2), low(G.size()), pre(G.size()),
        stk(G.size()) {
    for (int v = 0; v < int(G.size()); v++) if (id[v] == -2) {
      dfs(G, v, -1); if (top > 0) makeComponent(v);
    }
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../datastructures/unionfind/UnionFindUndo.h"
#include "../../queries/LIFOSetDivAndConq.h"
using namespace std;

// Support offline queries on connected components, after edges have been
//   added or removed, using divide and conquer
// Constructor Arguments:
//   V: the number of vertices in the graph
// Fields:
//   ans: a vector of integers with the answer for
//     each query (1 is true, 0 is false for boolean queries)
// Functions:
//   addEdge(v, w): adds an edge between vertices v and w
//   removeEdge(v, w): removes an edge between vertices v and w, assuming
//     an edge exists
//   addConnectedQuery(v, w): adds a query asking whether v and w are in the
//     same connected component
//   addSizeQuery(v): adds a query asking for the number of vertices in the
//     same connected component as vertex v
//   addCntQuery(): adds a query asking for the number of connected components
//   solveQueries(): solves all queries asked so far
// In practice, has a small constant, faster than DynamicConnectivityLCT and
//   DynamicConnectivityLevelStructure
// Time Complexity:
//   constructor: O(1)
//   addEdge, removeEdge, addConnectedQuery, addSizeQuery, addCntQuery: O(1)
//   solveQueries: O(V + Q log Q log V)
// Memory Complexity: O(V + Q) for Q edge additions/removals and queries
// Tested:
//   https://codeforces.com/gym/100551/problem/A
//   https://codeforces.com/gym/100551/problem/E
struct DynamicConnectivityDivAndConq {
  struct S {
    using T = pair<int, int>; using R = int;
    struct Q { int type, v, w; };
    UnionFindUndo uf;
    S(int V) : uf(V) {}
    void push(const T &e) { uf.join(e.first, e.second); }
    void pop() { uf.undo(); }
    R query(const Q &q) {
      if (q.type == 1) return uf.connected(q.v, q.w);
      else if (q.type == 2) return uf.getSize(q.v);
      else return uf.cnt;
    }
  };
  int V; LIFOSetDivAndConq<S> s; vector<int> &ans = s.ans;
  DynamicConnectivityDivAndConq(int V) : V(V) {}
  void addEdge(int v, int w) {
    if (v > w) swap(v, w);
    s.addElement(make_pair(v, w));
  }
  void removeEdge(int v, int w) {
    if (v > w) swap(v, w);
    s.removeElement(make_pair(v, w));
  }
  void addConnectedQuery(int v, int w) {
    S::Q q; q.type = 1; q.v = v; q.w = w; s.addQuery(q);
  }
  void addSizeQuery(int v) {
    S::Q q; q.type = 2; q.v = q.w = v; s.addQuery(q);
  }
  void addCntQuery() { S::Q q; q.type = 3; q.v = q.w = -1; s.addQuery(q); }
  void solveQueries() { s.solveQueries(V); }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../dynamictrees/LinkCutTree.h"
using namespace std;

// Support offline queries on connected components, after edges have been
//   added or removed, using a Link Cut Tree
// Constructor Arguments:
//   V: the number of vertices in the graph
// Fields:
//   ans: a vector of integers with the answer for
//     each query (1 is true, 0 is false for boolean queries)
// Functions:
//   addEdge(v, w): adds an edge between vertices v and w
//   removeEdge(v, w): removes an edge between vertices v and w, assuming
//     an edge exists
//   addConnectedQuery(v, w): adds a query asking whether v and w are in the
//     same connected component
//   addCntQuery(): adds a query asking for the number of connected components
//   solveQueries(): solves all queries asked so far
// In practice, has a moderate constant, slower than
//   DynamicConnectivityDivAndConq, faster than
//   DynamicConnectivityLevelStructure
// Time Complexity:
//   constructor: O(1)
//   addEdge, removeEdge, addConnectedQuery, addCntQuery: O(1)
//   solveQueries: O(V + Q (log Q + log V))
// Memory Complexity: O(V + Q) for Q edge additions/removals and queries
// Tested:
//   https://codeforces.com/gym/100551/problem/A
//   https://codeforces.com/gym/100551/problem/E
struct DynamicConnectivityLCT {
  struct Node {
    using Data = pair<int, int>; using Lazy = Data;
    static const bool RANGE_UPDATES = false, RANGE_QUERIES = true;
    static const bool RANGE_REVERSALS = true, HAS_PAR = true;
    bool rev; Node *l, *r, *p; Data val, sbtr;
    Node(const Data &v)
        : rev(false), l(nullptr), r(nullptr), p(nullptr), val(v), sbtr(v) {}
    void update() {
      sbtr = val;
      if (l) { sbtr = min(l->sbtr, sbtr); }
      if (r) { sbtr = min(sbtr, r->sbtr); }
    }
    void propagate() {
      if (rev) {
        swap(l, r); rev = false;
        if (l) l->reverse();
        if (r) r->reverse();
      }
    }
    void reverse() { rev = !rev; }
    static Data qdef() { return make_pair(INT_MAX, -1); }
  };
  int V; vector<tuple<int, int, int, int>> queries; vector<int> ans;
  DynamicConnectivityLCT(int V) : V(V) {}
  void addEdge(int v, int w) {
    if (v > w) swap(v, w);
    queries.emplace_back(0, v, w, -1);
  }
  void removeEdge(int v, int w) {
    if (v > w) swap(v, w);
    queries.emplace_back(1, v, w, -1);
  }
  void addConnectedQuery(int v, int w) {
    queries.emplace_back(2, v, w, queries.size());
  }
  void addCntQuery() { queries.emplace_back(3, -1, -1, queries.size()); }
  void solveQueries() {
    vector<pair<int, int>> edges; int Q = queries.size(); edges.reserve(Q);
    for (auto &&q : queries) if (get<0>(q) == 0)
      edges.emplace_back(get<1>(q), get<2>(q));
    sort(edges.begin(), edges.end()); vector<int> last(edges.size(), Q);
    for (int i = 0; i < Q; i++) {
      int t, v, w, _; tie(t, v, w, _) = queries[i]; if (t == 0) {
        int j = lower_bound(edges.begin(), edges.end(), make_pair(v, w))
            - edges.begin();
        get<3>(queries[i]) = last[j]; last[j] = i;
      } else if (t == 1) {
        int j = lower_bound(edges.begin(), edges.end(), make_pair(v, w))
            - edges.begin();
        int temp = get<3>(queries[get<3>(queries[i]) = last[j]]);
        get<3>(queries[last[j]]) = i; last[j] = temp;
      }
    }
    vector<pair<int, int>> tmp(V + Q, make_pair(INT_MAX, -1));
    for (int i = 0; i < Q; i++) tmp[V + i] = make_pair(get<3>(queries[i]), i);
    LCT<Node> lct(tmp); ans.clear(); for (int i = 0, cnt = V; i < Q; i++) {
      int t, v, w, o; tie(t, v, w, o) = queries[i]; if (t == 0) {
        if (v == w) continue;
        int z, j; tie(z, j) = lct.queryPath(v, w); if (j != -1) {
          if (z >= o) continue;
          lct.cut(get<1>(queries[j]), V + j);
          lct.cut(get<2>(queries[j]), V + j); cnt++;
        }
        lct.link(v, V + i); lct.link(w, V + i); cnt--;
      } else if (t == 1) {
        if (v == w) continue;
        if (lct.connected(v, V + o)) {
          lct.cut(v, V + o); lct.cut(w, V + o); cnt++;
        }
      } else if (t == 2) ans.push_back(lct.connected(v, w));
      else if (t == 3) ans.push_back(cnt);
    }
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../datastructures/unionfind/UnionFind.h"
using namespace std;

// Computes the connected components of a graph using Union Find
// Vertices are 0-indexed
// Constructor Arguments:
//   V: number of vertices in the graph
// Fields:
//   id: a vector of the index of the component each vertex is part of
//   components: a vector of vectors containing the vertices in each component
//   uf: a UnionFind data structure representing the connected components
// Functions:
//   addEdge: adds a bidirectional edge between vertices v and w
//   assign: assigns each vertex to a connected component and populates the
//     id and component vectors
// In practice, has a small constant, faster than bfs and dfs
// Time Complexity:
//   constructor: O((V + E) alpha V)
// Memory Complexity: O(V)
// Tested:
//   https://dmoj.ca/problem/ccc03s3
//   https://codeforces.com/contest/1253/problem/D
struct CC {
  int V; vector<int> id; vector<vector<int>> components; UnionFind uf;
  CC(int V) : V(V), id(V), uf(V) {}
  void addEdge(int v, int w) { uf.join(v, w); }
  void assign() {
    components.clear(); components.reserve(uf.cnt);
    fill(id.begin(), id.end(), -1);
    for (int v = 0; v < V; v++) if (uf.find(v) == v) {
      id[v] = components.size(); components.emplace_back(1, v);
      components.back().reserve(uf.getSize(v));
    }
    for (int v = 0; v < V; v++) if (id[v] == -1)
      components[id[v] = id[uf.find(v)]].push_back(v);
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../datastructures/unionfind/UnionFind.h"
#include "../../datastructures/unionfind/PartiallyPersistentUnionFind.h"
using namespace std;

// Supports persistent queries on 2-edge connected component after
//   edges have been added
// Constructor Arguments:
//   V: number of vertices in the graph
//   edges: a vector of pairs in the form (v, w) representing
//     an undirected edge in the graph between vertices v and w in the order
//     of the list
// Functions:
//   find(t, v): inherited from PartiallyPersistentUnionFind, finds an
//     arbitrary root of the 2-edge connected component containing vertex v,
//     after the edge at index t in edges is added
//   connected(t, v, w): inherited from PartiallyPersistentUnionFind,
//     returns true if v and w are in the 2-edge connected component, after the
//     edge at index t in edges is added, returns false otherwise
//   getSize(t, v): inherited from PartiallyPersistentUnionFind, returns the
//     size of the 2-edge connected component containing vertex v, after the
//     edge at index t in edges is added
//   getCnt(t): inherited from PartiallyPersistentUnionFind, returns the number
//     of 2-edge connected components, after the edge at index t in
//     edges is added
//   getFirst(v, w): inherited from PartiallyPersistentUnionFind, returns
//     the index of the first edge in edges that vertices v and w are in the
//     same 2-edge connected component, -1 if v == w and curTime + 1 if they
//     are never in the same 2-edge connected component
//   getBridgeCnt(t): returns the number of bridges in the graph, after the
//     edge at index t in edges is added
// In practice, constructor, find, connected, getSize, getCnt,
//   getBridgeCnt have a small constant, getFirst has a very small constant
// Time Complexity:
//   constructor: O(V alpha V + E log V)
//   find, join, connected, getSize, getCnt: O(log V)
//   getFirst: O(log V log E)
//   getBridgeCnt: O(1)
// Memory Complexity: O(V + E)
// Tested:
//   https://dmoj.ca/problem/mcco17d1p3
struct PartiallyPersistentIncrementalBridges
    : public PartiallyPersistentUnionFind {
  vector<int> bridgeCnt;
  PartiallyPersistentIncrementalBridges(int V,
                                        const vector<pair<int, int>> &edges)
      : PartiallyPersistentUnionFind(V), bridgeCnt(edges.size()) {
    int E = edges.size(); vector<bool> inForest(E);
    vector<int> par(V, -1), dep(V), st(V + 1, 0), mn(V), to(E * 2);
    function<void(int, int, int)> dfs = [&] (int v, int prev, int d) {
      par[v] = prev; dep[v] = d; for (int e = st[v]; e < st[v + 1]; e++) {
        int w = to[e]; if (w != prev) dfs(w, v, d + 1);
      }
    };
    UnionFind forest(V); for (int i = 0; i < E; i++)
      inForest[i] = forest.join(edges[i].first, edges[i].second);
    iota(mn.begin(), mn.end(), 0); for (int i = 0; i < E; i++)
      if (inForest[i]) { st[edges[i].first]++; st[edges[i].second]++; }
    partial_sum(st.begin(), st.end(), st.begin());
    for (int i = 0; i < E; i++) if (inForest[i]) {
      int v, w; tie(v, w) = edges[i]; to[--st[v]] = w; to[--st[w]] = v;
    }
    for (int v = 0; v < V; v++) if (par[v] == -1) dfs(v, -1, 0);
    for (int i = 0, curBridgeCnt = 0; i < E; i++) {
      if (inForest[i]) curBridgeCnt++;
      else {
        int v, w; tie(v, w) = edges[i];
        for (v = mn[find(i, v)], w = mn[find(i, w)]; v != w;) {
          if (dep[v] < dep[w]) swap(v, w);
          int p = mn[find(i, par[v])]; join(v, p); v = mn[find(i, v)] = p;
          curTime--; curBridgeCnt--;
        }
      }
      bridgeCnt[i] = curBridgeCnt; curTime++;
    }
  }
  int getBridgeCnt(int t) { return bridgeCnt[t]; }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../dynamictrees/LinkCutTree.h"
using namespace std;

// Support offline queries for the number of bridges in a graph, after edges
//   have been added or removed, using a Link Cut Tree
// Constructor Arguments:
//   V: the number of vertices in the graph
// Fields:
//   ans: a vector of integers with the answer for each query
// Functions:
//   addEdge(v, w): adds an edge between vertices v and w
//   removeEdge(v, w): removes an edge between vertices v and w, assuming
//     an edge exists
//   addBridgeQuery(): adds a query for the number of bridges in the graph
//   solveQueries(): solves all queries asked so far
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O(1)
//   addEdge, removeEdge, addBridgeQuery: O(1)
//   solveQueries: O(V + Q (log Q + log V))
// Memory Complexity: O(V + Q) for Q edge additions/removals and queries
// Tested:
//   https://codeforces.com/gym/100551/problem/D
struct DynamicBridges {
  struct Node {
    static constexpr const int NO_COVER = INT_MIN, NO_DEL = INT_MAX;
    static void check(int &a, const int &b) {
      if ((a > b && b != NO_COVER) || a == NO_COVER) a = b;
    }
    using Data = pair<int, int>; using Lazy = Data;
    static const bool RANGE_UPDATES = false, RANGE_QUERIES = true;
    static const bool RANGE_REVERSALS = true;
    bool isEdge, rev; Data val, sbtr;
    int edgeCnt, coveredCntSub, coverLazy, covered, coveredSub;
    Node *l, *r, *p;
    Node(const Data &v)
        : isEdge(false), rev(false), val(v), sbtr(v), edgeCnt(0),
          coveredCntSub(0), coverLazy(NO_COVER), covered(NO_COVER),
          coveredSub(NO_COVER), l(nullptr), r(nullptr), p(nullptr) {}
    int getCoveredCnt() {
      return coverLazy == NO_COVER ? coveredCntSub : edgeCnt;
    }
    void update() {
      edgeCnt = isEdge; coveredCntSub = isEdge && (covered != NO_COVER);
      coveredSub = covered; sbtr = val;
      if (l) {
        check(coveredSub, l->coveredSub); check(coveredSub, l->coverLazy);
        edgeCnt += l->edgeCnt; coveredCntSub += l->getCoveredCnt();
        sbtr = min(l->sbtr, sbtr);
      }
      if (r) {
        check(coveredSub, r->coveredSub); check(coveredSub, r->coverLazy);
        edgeCnt += r->edgeCnt; coveredCntSub += r->getCoveredCnt();
        sbtr = min(r->sbtr, sbtr);
      }
    }
    void propagate() {
      if (rev) {
        if (l) l->reverse();
        if (r) r->reverse();
        rev = false;
      }
      if (coverLazy != NO_COVER) {
        covered = max(covered, coverLazy); check(coveredSub, coverLazy);
        if (l) l->coverLazy = max(l->coverLazy, coverLazy);
        if (r) r->coverLazy = max(r->coverLazy, coverLazy);
        coveredCntSub = edgeCnt; coverLazy = NO_COVER;
      }
    }
    void removeCover(int cover) {
      if (coverLazy <= cover) coverLazy = NO_COVER;
      if (coveredSub == NO_COVER || coveredSub > cover) return;
      if (covered <= cover) covered = NO_COVER;
      if (l) l->removeCover(cover);
      if (r) r->removeCover(cover);
      propagate(); update();
    }
    void reverse() { rev = !rev; swap(l, r); }
    static Data qdef() { return make_pair(NO_DEL, -1); }
  };
  int V; vector<tuple<int, int, int, int>> queries; vector<int> ans;
  DynamicBridges(int V) : V(V) {}
  void addEdge(int v, int w) {
    if (v > w) swap(v, w);
    queries.emplace_back(0, v, w, -1);
  }
  void removeEdge(int v, int w) {
    if (v > w) swap(v, w);
    queries.emplace_back(1, v, w, -1);
  }
  void addBridgeQuery() { queries.emplace_back(2, -1, -1, -1); }
  void solveQueries() {
    vector<pair<int, int>> edges; int Q = queries.size(); edges.reserve(Q);
    for (auto &&q : queries) if (get<0>(q) == 0)
      edges.emplace_back(get<1>(q), get<2>(q));
    sort(edges.begin(), edges.end()); vector<int> last(edges.size(), Q);
    for (int i = 0; i < Q; i++) {
      int t, v, w, _; tie(t, v, w, _) = queries[i]; if (t == 0) {
        int j = lower_bound(edges.begin(), edges.end(), make_pair(v, w))
            - edges.begin();
        get<3>(queries[i]) = last[j]; last[j] = i;
      } else if (t == 1) {
        int j = lower_bound(edges.begin(), edges.end(), make_pair(v, w))
            - edges.begin();
        int temp = get<3>(queries[get<3>(queries[i]) = last[j]]);
        get<3>(queries[last[j]]) = i; last[j] = temp;
      }
    }
    vector<pair<int, int>> tmp(V + Q, make_pair(Node::NO_DEL, -1));
    for (int i = 0; i < Q; i++) tmp[V + i] = make_pair(get<3>(queries[i]), i);
    LCT<Node> lct(tmp); int bridgeCnt = 0; for (int i = 0; i < Q; i++)
       lct.TR[V + i].edgeCnt = int(lct.TR[V + i].isEdge = true);
    auto cover = [&] (int x, int y, int coverId) {
      lct.queryPath(x, y); bridgeCnt += lct.TR[y].getCoveredCnt();
      lct.TR[y].coverLazy = coverId;
      bridgeCnt -= lct.TR[y].getCoveredCnt();
    };
    auto uncover = [&] (int x, int y, int coverId) {
      lct.queryPath(x, y); bridgeCnt += lct.TR[y].getCoveredCnt();
      lct.TR[y].removeCover(coverId);
      bridgeCnt -= lct.TR[y].getCoveredCnt();
    };
    auto addTreeEdge = [&] (int v, int w, int i) {
      lct.link(v, V + i); lct.link(w, V + i); bridgeCnt++;
    };
    auto removeTreeEdge = [&] (int v, int w, int i) {
      lct.cut(v, V + i); lct.cut(w, V + i);
      bridgeCnt += lct.TR[V + i].getCoveredCnt() - 1;
    };
    ans.clear(); for (int i = 0; i < Q; i++) {
      int t, v, w, o; tie(t, v, w, o) = queries[i]; if (t == 0) {
        if (v == w) continue;
        int z, j; tie(z, j) = lct.queryPath(v, w);
        if (j == -1) addTreeEdge(v, w, i);
        else {
          if (z >= o) { cover(v, w, o); continue; }
          int x = get<1>(queries[j]), y = get<2>(queries[j]);
          removeTreeEdge(x, y, j); addTreeEdge(v, w, i); cover(x, y, z);
        }
      } else if (t == 1) {
        if (v == w) continue;
        if (lct.connected(v, V + o)) removeTreeEdge(v, w, o);
        else uncover(v, w, i);
      } else if (t == 2) ans.push_back(bridgeCnt);
    }
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../datastructures/unionfind/UnionFind.h"
using namespace std;

// Decomposes an undirected graph into 3-edge connected components
// Vertices are 0-indexed
// Constructor Arguments:
//   G: a generic undirected graph structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the graph
// Fields:
//   id: a vector of the index of the 3-edge connected component each vertex
//     is part of
//   components: a vector of vectors containing the vertices in each 3-edge
//     connected component
//   uf: a UnionFind data structure representing the 3-edge connected
//     components
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O((V + E) alpha V)
// Memory Complexity: O(V)
// Tested:
//   https://judge.yosupo.jp/problem/three_edge_connected_components
struct ThreeEdgeCC {
  int V, ind; vector<int> id, pre, post, low, deg, path;
  vector<vector<int>> components; UnionFind uf;
  template <class Graph> void dfs(const Graph &G, int v, int prev) {
    pre[v] = ++ind; for (int w : G[v]) if (w != v) {
      if (w == prev) { prev = -1; continue; }
      if (pre[w] != -1) {
        if (pre[w] < pre[v]) { deg[v]++; low[v] = min(low[v], pre[w]); }
        else {
          deg[v]--; int &u = path[v];
          for (; u != -1 && pre[u] <= pre[w] && pre[w] <= post[u];) {
            uf.join(v, u); deg[v] += deg[u]; u = path[u];
          }
        }
        continue;
      }
      dfs(G, w, v); if (path[w] == -1 && deg[w] <= 1) {
        deg[v] += deg[w]; low[v] = min(low[v], low[w]); continue;
      }
      if (deg[w] == 0) w = path[w];
      if (low[v] > low[w]) { low[v] = min(low[v], low[w]); swap(w, path[v]); }
      for (; w != -1; w = path[w]) { uf.join(v, w); deg[v] += deg[w]; }
    }
    post[v] = ind;
  }
  template <class Graph> ThreeEdgeCC(const Graph &G)
      : V(G.size()), ind(-1), id(V, -1), pre(V, -1), post(V), low(V, INT_MAX),
        deg(V, 0), path(V, -1), uf(V) {
    for (int v = 0; v < V; v++) if (pre[v] == -1) dfs(G, v, -1);
    components.reserve(uf.cnt);
    for (int v = 0; v < V; v++) if (uf.find(v) == v) {
      id[v] = components.size(); components.emplace_back(1, v);
      components.back().reserve(uf.getSize(v));
    }
    for (int v = 0; v < V; v++) if (id[v] == -1)
      components[id[v] = id[uf.find(v)]].push_back(v);
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../dynamictrees/LinkCutTree.h"
using namespace std;

// Support queries for the number of bridges in a graph, after edges have been
//   added, using a Link Cut Tree, as well as undoing the last edge added
// Constructor Arguments:
//   V: the number of vertices in the graph
// Fields:
//   bridgeCnt: the current number of bridges in the graph
//   history: a vector of tuples storing information of the last edge added
// Functions:
//   addEdge(v, w): adds an edge between vertices v and w
//   undo(v, w): undoes the last edge added to the graph
//   twoEdgeConnected(v, w): queries whether v and w are in the
//     same 2-edge connected component
// Time Complexity:
//   constructor: O(V)
//   addEdge, undo, twoEdgeConnected: O(log V) amortized
// Memory Complexity: O(V)
// Tested:
//   https://codeforces.com/gym/100551/problem/D
struct IncrementalBridgesUndo {
  struct Node {
    using Data = pair<int, int>; using Lazy = int;
    static const bool RANGE_UPDATES = true, RANGE_QUERIES = true;
    static const bool RANGE_REVERSALS = true;
    bool rev; int sz; Node *l, *r, *p; Lazy lz; Data val, sbtr;
    Node(const Data &v)
        : rev(false), sz(1), l(nullptr), r(nullptr), p(nullptr),
          lz(0), val(v), sbtr(v) {}
    void update() {
      sz = 1; sbtr = val;
      if (l) {
        sz += l->sz;
        if (sbtr.first < l->sbtr.first) sbtr = l->sbtr;
        else if (sbtr.first == l->sbtr.first) sbtr.second += l->sbtr.second;
      }
      if (r) {
        sz += r->sz;
        if (sbtr.first < r->sbtr.first) sbtr = r->sbtr;
        else if (sbtr.first == r->sbtr.first) sbtr.second += r->sbtr.second;
      }
    }
    void propagate() {
      if (rev) {
        if (l) l->reverse();
        if (r) r->reverse();
        rev = false;
      }
      if (lz != 0) {
        if (l) l->apply(lz);
        if (r) r->apply(lz);
        lz = 0;
      }
    }
    void apply(const Lazy &v) {
      lz += v; val.first += v; sbtr.first += v;
    }
    void reverse() { rev = !rev; swap(l, r); }
    static Data qdef() { return make_pair(0, 0); }
  };
  int V, treeEdges, bridgeCnt; LCT<Node> lct;
  vector<tuple<int, int, int>> history;
  vector<pair<int, int>> init(int V) {
    vector<pair<int, int>> ret(max(0, V * 2 - 1), make_pair(1, 1));
    fill(ret.begin(), ret.begin() + V, make_pair(0, 1)); return ret;
  }
  IncrementalBridgesUndo(int V)
      : V(V), treeEdges(0), bridgeCnt(0), lct(init(V)) {}
  void addEdge(int v, int w) {
    pair<int, int> q = lct.queryPath(v, w); if (q.second == 0) {
      lct.link(v, V + treeEdges); lct.link(w, V + treeEdges++); bridgeCnt++;
      history.emplace_back(v, w, -1); return;
    }
    lct.updatePathFromRoot(w, -1); if (q.first == 1) bridgeCnt -= q.second;
    history.emplace_back(v, w, q.first == 1 ? q.second : 0);
  }
  void undo() {
    int v, w, delta; tie(v, w, delta) = history.back(); history.pop_back();
    if (delta < 0) {
      lct.cut(v, V + --treeEdges); lct.cut(w, V + treeEdges); bridgeCnt--;
      return;
    }
    lct.updatePath(v, w, 1); bridgeCnt += delta;
  }
  bool twoEdgeConnected(int v, int w) {
    return lct.queryPath(v, w).first == 0;
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Computes the biconnected components of an undirected graph
// Vertices are 0-indexed
// Constructor Arguments:
//   G: a generic undirected graph structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the graph
//   blockCutForestEdges: a reference to a vector of pairs that will store the
//     edges in the block-cut forest with the articulation vertices having the
//     same index in the original graph, non articulation vertices being
//     isolated, and each bcc/block having an index offset by V
// Fields:
//   ids: a vector of vectors of the indices of the bccs each vertex is part of
//   components: a vector of vectors containing the vertices in each bcc
//   articulation: a vector of booleans that indicates whether each vertex
//     is an articulation point or not
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O(V + E)
// Memory Complexity: O(V + E)
// Tested:
//   Stress Tested
//   https://judge.yosupo.jp/problem/biconnected_components
struct BCC {
  int ind; vector<int> low, pre; vector<pair<int, int>> stk;
  vector<bool> articulation; vector<vector<int>> ids, components;
  vector<vector<pair<int, int>>> edgesInComp;
  void assign(int x, int id) {
    if (ids[x].empty() || ids[x].back() != id) {
      ids[x].push_back(id); components.back().push_back(x);
    }
  }
  void makeComponent(int s) {
    int x, y, id = components.size(); components.emplace_back();
    edgesInComp.emplace_back(); while (int(stk.size()) > s) {
      tie(x, y) = stk.back(); stk.pop_back(); assign(x, id); assign(y, id);
      edgesInComp.back().emplace_back(x, y);
    }
  }
  template <class Graph> void dfs(const Graph &G, int v, int prev) {
    low[v] = pre[v] = ind++; bool parEdge = false; int deg = 0;
    for (int w : G[v]) {
      deg++; if (w == prev && !parEdge) parEdge = true;
      else if (pre[w] == -1) {
        int s = stk.size(); stk.emplace_back(v, w);
        dfs(G, w, v); low[v] = min(low[v], low[w]);
        if (low[w] >= pre[v]) { articulation[v] = true; makeComponent(s); }
      } else {
        low[v] = min(low[v], pre[w]);
        if (pre[w] < pre[v]) stk.emplace_back(v, w);
      }
    }
    if (deg == 0) { makeComponent(0); assign(v, int(components.size()) - 1); }
  }
  template <class Graph> BCC(const Graph &G)
      : ind(0), low(G.size()), pre(G.size(), -1),
        articulation(G.size(), false), ids(G.size()) {
    for (int v = 0; v < int(G.size()); v++) if (pre[v] == -1) dfs(G, v, -1);
  }
  template <class Graph>
  BCC(const Graph &G, vector<pair<int, int>> &blockCutForestEdges) : BCC(G) {
    for (int v = 0; v < int(G.size()); v++) if (articulation[v])
      for (int id : ids[v])
        blockCutForestEdges.emplace_back(v, int(G.size()) + id);
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../datastructures/trees/binarysearchtrees/Splay.h"
using namespace std;

// Support online queries on connected components, after edges have been
//   added or removed, using a level structure (log V Euler Tour Trees)
// Constructor Arguments:
//   V: the number of vertices in the graph
// Fields:
//   cnt: the current number of connected components
// Functions:
//   addEdge(v, w): adds an edge between vertices v and w, assuming
//     no edges currently exists
//   removeEdge(v, w): removes an edge between vertices v and w, assuming
//     an edge exists
//   connected(v, w): returns true if v and w are in the same
//     connected component, false otherwise
//   getSize(v): returns the size of the connected component containing
//     vertex v
// In practice, has a moderate constant, slower than DynamicConnectivityLCT and
//   DynamicConnectivityDivAndConq
// Time Complexity:
//   constructor: O(V)
//   addEdge, connected, getSize: O(log V) amortized
//   removeEdge: O((log V)^2) amortized
// Memory Complexity: O((V + E) log V)
// Tested:
//   https://www.acmicpc.net/problem/17465
struct DynamicConnectivityLevelStructure {
  struct Node {
    int v, sz; Node *l, *r, *p;
    Node(int v) : v(v), sz(1), l(nullptr), r(nullptr), p(nullptr) {}
    void update() {
      sz = 1;
      if (l) sz += l->sz;
      if (r) sz += r->sz;
    }
    void propagate() {}
  };
  struct Level : public Splay<Node> {
    vector<map<int, Node *>> T; vector<set<int>> G; vector<int> vis; int stamp;
    Level(int V) : T(V), G(V), vis(V, -1), stamp(0) {}
    void insert(Node *&root, int i, Node *n) {
      applyToRange(root, i, i - 1, [&] (Node *&x) { x = n; });
    }
    Node *disconnect(Node *&root, int l, int r) {
      Node *ret = nullptr;
      applyToRange(root, l, r, [&] (Node *&x) { ret = x; x = nullptr; });
      return ret;
    }
    void makeRoot(int v) {
      if (!T[v].empty()) {
        Node *l = T[v].begin()->second; int i = index(l, l);
        Node *r = disconnect(l, i, l->sz - 1); insert(l, 0, r);
        splay(T[v].begin()->second);
      }
    }
    int findRoot(int v) {
      if (T[v].empty()) return v;
      Node *x = T[v].begin()->second; splay(x);
      for (x->propagate(); x->l; (x = x->l)->propagate());
      splay(x); return x->v;
    }
    bool connected(int v, int w) { return findRoot(v) == findRoot(w); }
    int getSize(int v) {
      if (T[v].empty()) return 0;
      Node *x = T[v].begin()->second; splay(x); return x->sz / 2 + 1;
    }
    bool addEdge(int v, int w) {
      G[v].insert(w); G[w].insert(v); if (!connected(v, w)) {
        makeRoot(v); makeRoot(w);
        Node *l = T[v].empty() ? nullptr : T[v].begin()->second;
        insert(l, l ? l->sz : 0, T[v][w] = makeNode(v));
        if (!T[w].empty()) insert(l, l->sz, T[w].begin()->second);
        insert(l, l->sz, T[w][v] = makeNode(w)); return true;
      }
      return false;
    }
    bool removeEdge(int v, int w) {
      G[v].erase(w); G[w].erase(v); auto it1 = T[v].find(w);
      if (it1 != T[v].end()) {
        auto it2 = T[w].find(v); Node *a = it1->second, *b = it2->second;
        int i = index(a, a), j = index(b, b); if (i > j) swap(i, j);
        Node *c = disconnect(b, i, j); clear(disconnect(c, 0, 0));
        clear(disconnect(c, c->sz - 1, c->sz - 1));
        T[v].erase(it1); T[w].erase(it2); return true;
      }
      return false;
    }
    void dfs(Node *x, vector<int> &verts) {
      if (!x) return;
      if (vis[x->v] != stamp) { vis[x->v] = stamp; verts.push_back(x->v); }
      dfs(x->l, verts); dfs(x->r, verts);
    }
    vector<int> vertsInComp(int v) {
      if (T[v].empty()) return vector<int>{v};
      vector<int> ret; Node *x = T[v].begin()->second; splay(x); dfs(x, ret);
      stamp++; return ret;
    }
  };
  int V, cnt; deque<Level> lvls;
  DynamicConnectivityLevelStructure(int V) : V(V), cnt(V), lvls(1, Level(V)) {}
  void addEdge(int v, int w) { cnt -= lvls[0].addEdge(v, w); }
  void removeEdge(int v, int w) {
    int i = -1; for (int j = 0; j < int(lvls.size()); j++)
      if (lvls[j].removeEdge(v, w)) i = j;
    if (i == -1) return;
    pair<int, int> f = make_pair(-1, -1); cnt++;
    for (; f.first == -1 && i >= 0; i--) {
      if (i + 1 == int(lvls.size())) lvls.emplace_back(V);
      if (lvls[i].getSize(v) > lvls[i].getSize(w)) swap(v, w);
      int r = lvls[i].findRoot(w); for (int x : lvls[i].vertsInComp(v)) {
        for (auto &&y : lvls[i].T[x]) lvls[i + 1].addEdge(x, y.first);
        for (int y : lvls[i].G[x]) {
          if (f.first == -1 && lvls[i].findRoot(y) == r) f = make_pair(x, y);
          else { lvls[i + 1].G[x].insert(y); lvls[i + 1].G[y].insert(x); }
        }
      }
    }
    if (f.first != -1)
      for (cnt--, i++; i >= 0; i--) lvls[i].addEdge(f.first, f.second);
  }
  bool connected(int v, int w) { return lvls[0].connected(v, w); }
  int getSize(int v) { return lvls[0].getSize(v); }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../datastructures/unionfind/UnionFind.h"
using namespace std;

// Computes the minimum spanning tree (or forest) using Kruskal's algorithm
// Vertices are 0-indexed
// Template Arguments:
//   T: the type of the weight of the edges
// Constructor Arguments:
//   V: number of vertices in the graph
//   edges: a vector of tuples in the form (v, w, weight) representing
//     an undirected edge in the graph between vertices v and w with
//     weight of weight
// Fields:
//   mstWeight: the weight of the mst
//   mstEdges: a vector of tuples of the edges in the mst
// In practice, has a small constant, faster than Prim and Boruvka
// Time Complexity:
//   constructor: O(V + E log E)
// Memory Complexity: O(V + E)
// Tested:
//   Stress Tested
//   https://open.kattis.com/problems/minspantree
template <class T> struct KruskalMST {
  using Edge = tuple<int, int, T>;
  T mstWeight; vector<Edge> mstEdges; UnionFind uf;
  KruskalMST(int V, vector<Edge> edges) : mstWeight(), uf(V) {
    sort(edges.begin(), edges.end(), [&] (const Edge &a, const Edge &b) {
      return get<2>(a) < get<2>(b);
    });
    for (auto &&e : edges) {
      if (int(mstEdges.size()) >= V - 1) break;
      if (uf.join(get<0>(e), get<1>(e))) {
        mstEdges.push_back(e); mstWeight += get<2>(e);
      }
    }
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Computes the minimum spanning tree (or forest) using Prims's algorithm
// Vertices are 0-indexed
// Template Arguments:
//   T: the type of the weight of the edges
// Constructor Arguments:
//   G: a generic weighted graph structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of pair<int, T> with weights of type T)
//       size() const: returns the number of vertices in the graph
//   INF: a value for infinity
// Fields:
//   mstWeight: the weight of the mst
//   mstEdges: a vector of tuples of the edges in the mst
// In practice, has a small constant, faster than Boruvka, slower that Kruskal
// Time Complexity:
//   constructor: O((V + E) log E)
// Memory Complexity: O(V + E)
// Tested:
//   Stress Tested
//   https://open.kattis.com/problems/minspantree
template <class T> struct PrimMST {
  using Edge = tuple<int, int, T>; T mstWeight; vector<Edge> mstEdges;
  struct Node {
    T d; int v; Node(T d, int v) : d(d), v(v) {}
    bool operator < (const Node &o) const { return d > o.d; }
  };
  template <class WeightedGraph>
  PrimMST(const WeightedGraph &G, T INF = numeric_limits<T>::max())
      : mstWeight() {
    int V = G.size(); vector<bool> done(V, false);
    vector<T> mn(V, INF); vector<int> to(V, -1); std::priority_queue<Node> PQ;
    for (int s = 0; s < V; s++) if (!done[s]) {
      PQ.emplace(mn[s] = T(), s); while (!PQ.empty()) {
        int v = PQ.top().v; PQ.pop(); if (done[v]) continue;
        done[v] = true;
        for (auto &&e : G[v]) if (!done[e.first] && e.second < mn[e.first]) {
          to[e.first] = v; PQ.emplace(mn[e.first] = e.second, e.first);
        }
      }
    }
    for (int v = 0; v < V; v++) if (to[v] != -1) {
      mstEdges.emplace_back(v, to[v], mn[v]); mstWeight += mn[v];
    }
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../datastructures/unionfind/UnionFind.h"
using namespace std;

// Computes the minimum spanning tree (or forest) using Boruvka's algorithm
// Vertices are 0-indexed
// Template Arguments:
//   T: the type of the weight of the edges
// Constructor Arguments:
//   V: number of vertices in the graph
//   edges: a vector of tuples in the form (v, w, weight) representing
//     an undirected edge in the graph between vertices v and w with
//     weight of weight
// Fields:
//   mstWeight: the weight of the mst
//   mstEdges: a vector of tuples of the edges in the mst
// In practice, has a small constant, slower than Prim and Kruskal
// Time Complexity:
//   constructor: O(V + E log V)
// Memory Complexity: O(V)
// Tested:
//   Stress Tested
//   https://open.kattis.com/problems/minspantree
template <class T> struct BoruvkaMST {
  using Edge = tuple<int, int, T>;
  T mstWeight; vector<Edge> mstEdges; UnionFind uf;
  BoruvkaMST(int V, const vector<Edge> &edges) : mstWeight(), uf(V) {
    for (int t = 1; t < V && int(mstEdges.size()) < V - 1; t *= 2) {
      vector<int> closest(V, -1); for (int e = 0; e < int(edges.size()); e++) {
        int v = uf.find(get<0>(edges[e])), w = uf.find(get<1>(edges[e]));
        if (v == w) continue;
        if (closest[v] == -1 || get<2>(edges[e]) < get<2>(edges[closest[v]]))
          closest[v] = e;
        if (closest[w] == -1 || get<2>(edges[e]) < get<2>(edges[closest[w]]))
          closest[w] = e;
      }
      for (int v = 0; v < V; v++) if (closest[v] != -1
          && uf.join(get<0>(edges[closest[v]]), get<1>(edges[closest[v]]))) {
        mstEdges.push_back(edges[closest[v]]);
        mstWeight += get<2>(edges[closest[v]]);
      }
    }
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../datastructures/trees/heaps/SkewHeapIncremental.h"
#include "../../datastructures/unionfind/UnionFindUndo.h"
using namespace std;

// Computes the minimum arborescence, or directed minimum spanning tree using
//   Gabow's variant of Edmonds' algorithm
// The directed minimum spanning tree is a set of edges such that every vertex
//   is reachable from the root, the sum of the edge weights is minimized
// Template Arguments:
//   T: the type of the weight of the edges
// Constructor Arguments:
//   V: number of vertices in the directed graph
//   edges: a vector of tuples in the form (v, w, weight) representing
//     a directed edge in the graph from vertex v to w with
//     weight of weight
//   root: the root of the directed mst to find
//   INF: a value for infinity
// Fields:
//   mstWeight: the weight of the directed mst, or INF if none exist
//   mstEdges: a vector of tuples of the edges in the directed mst
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O((V + E) log V)
// Memory Complexity: O(V + E)
// Tested:
//   https://open.kattis.com/contests/nwerc18open/problems/fastestspeedrun
//   https://codeforces.com/contest/240/problem/E
//   https://judge.yosupo.jp/problem/directedmst
template <class T> struct GabowMinArborescence {
  using Edge = tuple<int, int, T>;
  struct Pair {
    Edge e; int ind;
    Pair(const Edge &e, int ind) : e(e), ind(ind) {}
    bool operator > (const Pair &p) const { return get<2>(e) > get<2>(p.e); }
    Pair &operator += (const T &add) { get<2>(e) += add; return *this; }
  };
  using Heap = SkewHeapIncremental<Pair, greater<Pair>, T>;
  T INF, mstWeight; vector<Edge> mstEdges;
  GabowMinArborescence(int V, const vector<Edge> &edges, int root,
                       T INF = numeric_limits<T>::max())
      : INF(INF), mstWeight() {
    UnionFindUndo uf(V); vector<int> vis(V, -1); vis[root] = root;
    vector<Edge> in(V, Edge(-1, -1, T())); vector<Heap> H(V);
    for (int i = 0; i < int(edges.size()); i++)
      H[get<1>(edges[i])].push(Pair(edges[i], i));
    vector<tuple<int, int, vector<Edge>>> cycs; for (int s = 0; s < V; s++) {
      int v = s; vector<pair<int, Edge>> path; while (vis[v] < 0) {
        if (H[v].empty()) { mstWeight = INF; return; }
        vis[v] = s; Pair p = H[v].pop(); path.emplace_back(v, edges[p.ind]);
        H[v].increment(-get<2>(p.e)); v = uf.find(get<0>(p.e));
        mstWeight += get<2>(p.e); if (vis[v] == s) {
          Heap h; vector<Edge> E; int w, t = uf.history.size(); do {
            h.merge(H[w = path.back().first]);
            E.push_back(path.back().second); path.pop_back();
          } while (uf.join(v, w));
          H[v = uf.find(v)] = move(h); vis[v] = -1; cycs.emplace_back(v, t, E);
        }
      }
      for (auto &&p : path) in[uf.find(get<1>(p.second))] = p.second;
    }
    while (!cycs.empty()) {
      int v, t; vector<Edge> E; tie(v, t, E) = cycs.back(); cycs.pop_back();
      while (int(uf.history.size()) > t) uf.undo();
      Edge inEdge = in[v]; for (auto &&e : E) in[uf.find(get<1>(e))] = e;
      in[uf.find(get<1>(inEdge))] = inEdge;
    }
    for (int v = 0; v < V; v++)
      if (get<1>(in[v]) != -1) mstEdges.push_back(in[v]);
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../datastructures/unionfind/UnionFindUndo.h"
using namespace std;

// Support offline queries for the minimum spanning tree, after edges have been
//   added or removed, using divide and conquer and UnionFindUndo
// Template Arguments:
//   T: the type of the weight of the edges
// Constructor Arguments:
//   V: number of vertices in the graph
// Fields:
//   ans: a vector of type T with the minimum spanning tree for each query
// Functions:
//   addEdge(v, w, weight): adds an edge between vertices v and w with
//     a weight of weight
//   removeEdge(v, w, weight): removes an edge between vertices v and w with
//     a weight of weight, assuming such an edge exists
//   addMstQuery(v, w): adds a query asking for the current minimum spanning
//     tree (or forest)
//   solveQueries(): solves all queries asked so far
// In practice, has a small constant
// Time Complexity:
//   constructor: O(V)
//   addEdge, removeEdge, addMstQuery: O(1)
//   solveQueries: O(V + Q log Q (log Q + log V))
// Memory Complexity: O(V + Q) for Q edge additions/removals and queries
// Tested:
//   https://dmoj.ca/problem/ccoprep4p3
template <class T> struct DynamicMSTDivAndConq {
  int V; vector<tuple<int, int, int, T, int>> queries; vector<T> ans;
  DynamicMSTDivAndConq(int V) : V(V) {}
  void addEdge(int v, int w, T weight) {
    if (v > w) swap(v, w);
    queries.emplace_back(0, v, w, weight, -1);
  }
  void removeEdge(int v, int w, T weight) {
    if (v > w) swap(v, w);
    queries.emplace_back(1, v, w, weight, -1);
  }
  void addMstQuery() {
    queries.emplace_back(2, -1, -1, T(), -1);
  }
  void solveQueries() {
    vector<tuple<int, int, T>> edges; int Q = queries.size(); edges.reserve(Q);
    for (auto &&q : queries) if (get<0>(q) == 0)
      edges.emplace_back(get<1>(q), get<2>(q), get<3>(q));
    sort(edges.begin(), edges.end());
    vector<int> cntAdd(edges.size(), 0), cntRem = cntAdd, qinds{-1};
    qinds.reserve(Q); for (int i = 0; i < Q; i++) {
      int t, v, w, _; T weight; tie(t, v, w, weight, _) = queries[i];
      tuple<int, int, T> e(v, w, weight); if (t == 0) {
        int j = lower_bound(edges.begin(), edges.end(), e) - edges.begin();
        get<4>(queries[i]) = j + cntAdd[j]++;
      } else if (t == 1) {
        int j = lower_bound(edges.begin(), edges.end(), e) - edges.begin();
        get<4>(queries[i]) = j + cntRem[j]++;
      } else if (t == 2) qinds.push_back(i);
    }
    UnionFindUndo uf(V); ans.clear(); ans.reserve(Q);
    vector<bool> active(edges.size(), false), changed(edges.size(), false);
    auto cmpEdge = [&] (int i, int j) {
      return active[i] == active[j] ? get<2>(edges[i]) < get<2>(edges[j])
                                    : active[i];
    };
    function<void(int, int, vector<int> &, T)> dc
        = [&] (int ql, int qr, vector<int> &maybe, T curMST) {
      int curSize = uf.history.size(); if (ql == qr) {
        for (int i = qinds[ql - 1] + 1; i <= qinds[qr]; i++) {
          int t = get<0>(queries[i]), j = get<4>(queries[i]);
          if (t == 0) active[j] = true;
          else if (t == 1) active[j] = false;
          else if (t == 2) {
            sort(maybe.begin(), maybe.end(), cmpEdge); for (int j : maybe)
              if (active[j] && uf.join(get<0>(edges[j]), get<1>(edges[j])))
                curMST += get<2>(edges[j]);
            ans.push_back(curMST);
            while (int(uf.history.size()) > curSize) uf.undo();
          }
        }
        return;
      }
      sort(maybe.begin(), maybe.end(), cmpEdge);
      for (int i = qinds[ql - 1] + 1; i <= qinds[qr]; i++)
        if (get<0>(queries[i]) <= 1) {
          int j = get<4>(queries[i]); changed[j] = true;
          uf.join(get<0>(edges[j]), get<1>(edges[j]));
        }
      vector<int> must; for (int j : maybe)
        if (!changed[j] && uf.join(get<0>(edges[j]), get<1>(edges[j])))
          must.push_back(j);
      while (int(uf.history.size()) > curSize) uf.undo();
      for (int j : must) if (uf.join(get<0>(edges[j]), get<1>(edges[j])))
        curMST += get<2>(edges[j]);
      int curSize2 = uf.history.size();
      vector<int> newMaybe; for (int j : maybe)
        if (changed[j] || uf.join(get<0>(edges[j]), get<1>(edges[j])))
          newMaybe.push_back(j);
      while (int(uf.history.size()) > curSize2) uf.undo();
      for (int i = qinds[ql - 1] + 1; i <= qinds[qr]; i++)
        if (get<0>(queries[i]) <= 1) changed[get<4>(queries[i])] = false;
      int qm = ql + (qr - ql) / 2;
      dc(ql, qm, newMaybe, curMST); dc(qm + 1, qr, newMaybe, curMST);
      while (int(uf.history.size()) > curSize) uf.undo();
    };
    if (int(qinds.size()) > 1) {
      vector<int> maybe(edges.size()); iota(maybe.begin(), maybe.end(), 0);
      dc(1, int(qinds.size()) - 1, maybe, T());
    }
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../dynamictrees/LinkCutTree.h"
using namespace std;

// Supports queries for the minimum spanning tree (or forest) after
//   edges have been added, using a Link Cut Tree
// Template Arguments:
//   T: the type of the weight of the edges
// Constructor Arguments:
//   V: number of vertices in the graph
//   NEG_INF: a value for negative infinity of type T
// Fields:
//   mstWeight: the weight of the current mst
//   mstEdges: a vector of tuples of the edges in the current mst in the form
//     (v, w, weight) representing an undirected edge in the graph between
//     vertices v and w with weight of weight
//   lct: a Link Cut Tree of the current mst of the graph
// Functions:
//   addEdge(v, w, weight): adds an undirected edge in the graph between
//     vertices v and w with weight of weight
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O(V)
//   addEdge: O(log V) amortized
// Memory Complexity: O(V)
// Tested:
//   https://dmoj.ca/problem/noi14p2
//   https://open.kattis.com/problems/minspantree
//   https://codeforces.com/gym/101047/problem/I
template <class T> struct IncrementalMST {
  struct Node {
    using Data = pair<T, int>; using Lazy = Data;
    static const bool RANGE_UPDATES = false, RANGE_QUERIES = true;
    static const bool RANGE_REVERSALS = true;
    bool rev; Node *l, *r, *p; Data val, sbtr;
    Node(const Data &v)
        : rev(false), l(nullptr), r(nullptr), p(nullptr), val(v), sbtr(v) {}
    void update() {
      sbtr = val;
      if (l) { sbtr = max(l->sbtr, sbtr); }
      if (r) { sbtr = max(sbtr, r->sbtr); }
    }
    void propagate() {
      if (rev) {
        if (l) l->reverse();
        if (r) r->reverse();
        rev = false;
      }
    }
    void apply(const Lazy &v) { val = sbtr = v; }
    void reverse() { rev = !rev; swap(l, r); }
    static Data qdef() { return make_pair(T(), -1); }
  };
  using Edge = tuple<int, int, T>; int V, top; vector<int> stk;
  T mstWeight; vector<Edge> mstEdges; LCT<Node> lct;
  IncrementalMST(int V, T NEG_INF = numeric_limits<T>::lowest())
      : V(V), top(max(0, V - 1)), stk(top), mstWeight(T()),
        lct(vector<pair<T, int>>(V + top, make_pair(NEG_INF, -1))) {
    iota(stk.rbegin(), stk.rend(), 0); mstEdges.reserve(top);
  }
  void addEdge(int v, int w, T weight) {
    if (v == w) return;
    T z; int j; tie(z, j) = lct.queryPath(v, w); if (j != -1) {
      if (z <= weight) return;
      lct.cut(get<0>(mstEdges[j]), V + j); lct.cut(get<1>(mstEdges[j]), V + j);
      stk[top++] = j; mstWeight -= z;
    }
    j = stk[--top]; Edge e(v, w, weight);
    if (j >= int(mstEdges.size())) mstEdges.push_back(e);
    else mstEdges[j] = e;
    lct.updateVertex(V + j, make_pair(weight, j));
    lct.link(v, V + j); lct.link(w, V + j); mstWeight += weight;
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../dynamictrees/LinkCutTree.h"
using namespace std;

// Supports queries for the minimum spanning tree (or forest) after
//   edges have been added, using a Link Cut Tree, as well as undoing the
//   last edge added
// Template Arguments:
//   T: the type of the weight of the edges
// Constructor Arguments:
//   V: number of vertices in the graph
//   NEG_INF: a value for negative infinity of type T
// Fields:
//   mstWeight: the weight of the current mst
//   mstEdges: a vector of tuples of the edges in the current mst in the form
//     (v, w, weight) representing an undirected edge in the graph between
//     vertices v and w with weight of weight
//   lct: a Link Cut Tree of the current mst of the graph
//   history: a vector of tuples storing information of the last edge added
// Functions:
//   addEdge(v, w, weight): adds an undirected edge in the graph between
//     vertices v and w with weight of weight
//   undo(): undoes the last edge added to the graph
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O(V)
//   addEdge, undo: O(log V) amortized
// Memory Complexity: O(V)
// Tested:
//   https://dmoj.ca/problem/ccoprep4p3
template <class T> struct IncrementalMSTUndo {
  struct Node {
    using Data = pair<T, int>; using Lazy = Data;
    static const bool RANGE_UPDATES = false, RANGE_QUERIES = true;
    static const bool RANGE_REVERSALS = true;
    bool rev; Node *l, *r, *p; Data val, sbtr;
    Node(const Data &v)
        : rev(false), l(nullptr), r(nullptr), p(nullptr), val(v), sbtr(v) {}
    void update() {
      sbtr = val;
      if (l) { sbtr = max(l->sbtr, sbtr); }
      if (r) { sbtr = max(sbtr, r->sbtr); }
    }
    void propagate() {
      if (rev) {
        if (l) l->reverse();
        if (r) r->reverse();
        rev = false;
      }
    }
    void apply(const Lazy &v) { val = sbtr = v; }
    void reverse() { rev = !rev; swap(l, r); }
    static Data qdef() { return make_pair(T(), -1); }
  };
  using Edge = tuple<int, int, T>; int V, top; vector<int> stk;
  T mstWeight; vector<Edge> mstEdges; LCT<Node> lct;
  vector<tuple<int, Edge, int, Edge, bool>> history;
  IncrementalMSTUndo(int V, T NEG_INF = numeric_limits<T>::lowest())
      : V(V), top(max(0, V - 1)), stk(top), mstWeight(T()),
        lct(vector<pair<T, int>>(V + top, make_pair(NEG_INF, -1))) {
    iota(stk.rbegin(), stk.rend(), 0); mstEdges.reserve(top);
  }
  void addEdge(int v, int w, T weight) {
    Edge e(v, w, weight); history.emplace_back(-1, e, -1, e, false);
    if (v == w) return;
    T z; int j; tie(z, j) = lct.queryPath(v, w); if (j != -1) {
      if (z <= weight) return;
      lct.cut(get<0>(mstEdges[j]), V + j); lct.cut(get<1>(mstEdges[j]), V + j);
      get<0>(history.back()) = stk[top++] = j; mstWeight -= z;
      get<1>(history.back()) = mstEdges[j];
    }
    get<2>(history.back()) = j = stk[--top]; if (j >= int(mstEdges.size())) {
      mstEdges.push_back(e); get<4>(history.back()) = true;
    } else mstEdges[j] = e;
    lct.updateVertex(V + j, make_pair(weight, j)); lct.link(v, V + j);
    lct.link(w, V + j); mstWeight += weight; get<3>(history.back()) = e;
  }
  void undo() {
    int j = get<2>(history.back()); Edge e = get<3>(history.back());
    if (j != -1) {
      mstWeight -= get<2>(e); stk[top++] = j;
      lct.cut(get<0>(e), V + j); lct.cut(get<1>(e), V + j);
      if (get<4>(history.back())) mstEdges.pop_back();
    }
    j = get<0>(history.back()); e = get<1>(history.back()); if (j != -1) {
      mstWeight += get<2>(e); --top; mstEdges[j] = e;
      lct.updateVertex(V + j, make_pair(get<2>(e), j));
      lct.link(get<0>(e), V + j); lct.link(get<1>(e), V + j);
    }
    history.pop_back();
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Computes the minimum spanning tree (or forest) using Classical Prims's
//   algorithm
// Vertices are 0-indexed
// Constructor Arguments:
//   G: a generic weighted graph structure
//     with the [] operator (const) defined to iterate over the adjacency list
//     (which is a list of pair<int, T> with weights of type T), as well as a
//     member function size() (const) that returns the number of vertices
//     in the graph
//   INF: a value for infinity
// Fields:
//   mstWeight: the weight of the mst
//   mstEdges: a vector of tuples of the edges in the mst
// In practice, has a small constant
// Time Complexity:
//   constructor: O(V^2 + E)
// Memory Complexity: O(V + E)
// Tested:
//   Stress Tested
//   https://mcpt.ca/problem/anmstproblem
template <class T> struct ClassicalPrimMST {
  using Edge = tuple<int, int, T>; T mstWeight; vector<Edge> mstEdges;
  template <class WeightedGraph>
  ClassicalPrimMST(const WeightedGraph &G, T INF = numeric_limits<T>::max())
      : mstWeight() {
    int V = G.size(); vector<bool> done(V, false); vector<T> mn(V, INF);
    vector<int> to(V, -1); for (int s = 0; s < V; s++) if (!done[s]) {
      mn[s] = T(); while (true) {
        int v = -1; for (int w = 0; w < V; w++)
          if (!done[w] && (v == -1 || mn[v] > mn[w])) v = w;
        if (v == -1 || mn[v] >= INF) break;
        done[v] = true;
        for (auto &&e : G[v]) if (!done[e.first] && e.second < mn[e.first]) {
          to[e.first] = v; mn[e.first] = e.second;
        }
      }
    }
    for (int v = 0; v < V; v++) if (to[v] != -1) {
      mstEdges.emplace_back(v, to[v], mn[v]); mstWeight += mn[v];
    }
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "KruskalMST.h"
using namespace std;

// Computes the minimum spanning tree of a complete graph of N points where
//   the edge weights is equal to the Manhattan distance between the
//   points |x_i - x_j| + |y_i - y_j|
// Generates up to 4N candidate edges with each point connected to its nearest
//   neighbour in each octant
// Vertices are 0-indexed
// Template Arguments:
//   T: the type of the coordinates of the points
// Constructor Arguments:
//   P: a vector of pairs of type T representing the points
// Fields:
//   mstWeight: the weight of the mst
//   mstEdges: a vector of tuples of the edges in the mst with the vertices
//     corresponding to the original indices of P
// In practice, has a moderate constant
// Time Complexity: O(N log N)
// Memory Complexity: O(N)
// Tested:
//   https://judge.yosupo.jp/problem/manhattanmst
template <class T> struct ManhattanMST : public KruskalMST<T> {
  using Edge = typename KruskalMST<T>::Edge;
  static vector<Edge> generateCandidates(vector<pair<T, T>> P) {
    vector<int> id(P.size()); iota(id.begin(), id.end(), 0); vector<Edge> ret;
    ret.reserve(P.size() * 4); for (int h = 0; h < 4; h++) {
      sort(id.begin(), id.end(), [&] (int i, int j) {
        return P[i].first - P[j].first < P[j].second - P[i].second;
      });
      map<T, int> M; for (int i : id) {
        auto it = M.lower_bound(-P[i].second);
        for (; it != M.end(); it = M.erase(it)) {
          int j = it->second;
          T dx = P[i].first - P[j].first, dy = P[i].second - P[j].second;
          if (dy > dx) break;
          ret.emplace_back(i, j, dx + dy);
        }
        M[-P[i].second] = i;
      }
      for (auto &&p : P) {
        if (h % 2) p.first = -p.first;
        else swap(p.first, p.second);
      }
    }
    return ret;
  }
  ManhattanMST(const vector<pair<T, T>> &P)
      : KruskalMST<T>(P.size(), generateCandidates(P)) {}
};


text:
#pragma once
#include <bits/stdc++.h>
#include "IncrementalBipartiteUndo.h"
#include "../../queries/LIFOSetDivAndConq.h"
using namespace std;

// Support offline queries on connected components and bipartiteness, after
//   edges have been added or removed, using divide and conquer
// Constructor Arguments:
//   V: the number of vertices in the graph
// Fields:
//   ans: a vector of integers with the answer for
//     each query (1 is true, 0 is false for boolean queries)
// Functions:
//   addEdge(v, w): adds an edge between vertices v and w
//   removeEdge(v, w): removes an edge between vertices v and w, assuming
//     an edge exists
//   addConnectedQuery(v, w): adds a query asking whether v and w are in the
//     same connected component
//   addSizeQuery(v): adds a query asking for the number of vertices in the
//     same connected component as vertex v
//   addCntQuery(): adds a query asking for the number of connected components
//   addComponentBipartiteQuery(v): adds a query asking for whether the
//     connected component containing vertex v is bipartite
//   addBipartiteGraphQuery(): adds a query asking if the graph is bipartite
//   addColorQuery(v): adds a query asking for the color of vertex v for one
//     possible coloring of the graph, assuming the component is bipartite
//   addPathParityQuery(v, w): adds a query asking for the parity of the path
//     from v to w (false if even number of edges, true if odd), assuming the
//     component is bipartite and v and w are connected
//   solveQueries(): solves all queries asked so far
// In practice, has a small constant
// Time Complexity:
//   constructor: O(1)
//   addEdge, removeEdge, addConnectedQuery, addSizeQuery, addCntQuery: O(1)
//   addComponentBipartiteQuery, addBipartiteGraphQuery: O(1)
//   addColorQuery, addPathParity: O(1)
//   solveQueries: O(V + Q log Q log V)
// Memory Complexity: O(V + Q) for Q edge additions/removals and queries
// Tested:
//   https://codeforces.com/contest/813/problem/F
struct DynamicBipartiteDivAndConq {
  struct S {
    using T = pair<int, int>; using R = int;
    struct Q { int type, v, w; };
    IncrementalBipartiteUndo uf;
    S(int V) : uf(V) {}
    void push(const T &e) { uf.addEdge(e.first, e.second); }
    void pop() { uf.undo(); }
    R query(const Q &q) {
      if (q.type == 1) return uf.connected(q.v, q.w);
      else if (q.type == 2) return uf.getSize(q.v);
      else if (q.type == 3) return uf.cnt;
      else if (q.type == 4) return uf.componentBipartite(q.v);
      else if (q.type == 5) return uf.bipartiteGraph;
      else if (q.type == 6) return uf.color(q.v);
      else return uf.pathParity(q.v, q.w);
    }
  };
  int V; LIFOSetDivAndConq<S> s; vector<int> &ans = s.ans;
  DynamicBipartiteDivAndConq(int V) : V(V) {}
  void addEdge(int v, int w) {
    if (v > w) swap(v, w);
    s.addElement(make_pair(v, w));
  }
  void removeEdge(int v, int w) {
    if (v > w) swap(v, w);
    s.removeElement(make_pair(v, w));
  }
  void addConnectedQuery(int v, int w) {
    S::Q q; q.type = 1; q.v = v; q.w = w; s.addQuery(q);
  }
  void addSizeQuery(int v) {
    S::Q q; q.type = 2; q.v = q.w = v; s.addQuery(q);
  }
  void addCntQuery() { S::Q q; q.type = 3; q.v = q.w = -1; s.addQuery(q); }
  void addComponentBipartiteQuery(int v) {
    S::Q q; q.type = 4; q.v = q.w = v; s.addQuery(q);
  }
  void addBipartiteGraphQuery() {
    S::Q q; q.type = 5; q.v = q.w = -1; s.addQuery(q);
  }
  void addColorQuery(int v) {
    S::Q q; q.type = 6; q.v = q.w = v; s.addQuery(q);
  }
  void addPathParityQuery(int v, int w) {
    S::Q q; q.type = 7; q.v = v; q.w = w; s.addQuery(q);
  }
  void solveQueries() { s.solveQueries(V); }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Supports queries for whether a graph component is bipartite
//   after edges have been added using Union Find by size supporting undos
// Vertices are 0-indexed
//   V: the number of vertices in the graph
// Fields:
//   UF: a vector of integers representing the parent of each vertex in the
//     tree, or the negative of the size of the connected component if that
//     vertex is a root
//   P: a vector of booleans representing the parity of the path to the root
//     of that connected component
//   B: a vector of booleans representing whether the component rooted at the
//     vertex is bipartite for root vertices, undefined otherwise
//   cnt: the current number of connected components
//   bipartiteGraph: a boolean indicating whether the current graph is
//     bipartite or not
//   history: a vector of tuples storing the history of all addEdge calls
// Functions:
//   find(v): returns a pair containing the root of the connected component and
//     the parity of the path from the root to vertex v
//   addEdge(v, w): adds an edge between vertices v and w
//   undo(): undoes the last edge added by popping from the history stack
//   connected(v, w): returns true if v and w are in the same
//     connected component, false otherwise
//   getSize(v): returns the size of the connected component containing
//     vertex v
//   componentBipartite(v): returns whether the connected component containing
//     vertex v is bipartite or not
//   color(v): returns the color of vertex v for one
//     possible coloring of the graph, assuming the component is bipartite
//   pathParity(v, w): return the parity of the path from
//     v to w (false if even number of edges, true if odd), assuming the
//     component is bipartite and v and w are connected
// Time Complexity:
//   constructor: O(V)
//   find, addEdge, connected, getSize: O(log V)
//   componentBipartite, color, pathParity: O(log V)
//   undo: O(1)
// Memory Complexity: O(V + Q) for Q calls to addEdge
// Tested:
//   https://www.spoj.com/problems/BUGLIFE/
//   https://cses.fi/problemset/task/1668
//   https://codeforces.com/contest/813/problem/F
struct IncrementalBipartiteUndo {
  vector<int> UF; vector<bool> P, B; int cnt; bool bipartiteGraph;
  vector<tuple<int, int, int, bool, bool>> history;
  IncrementalBipartiteUndo(int V)
      : UF(V, -1), P(V, false), B(V, true), cnt(V), bipartiteGraph(true) {}
  pair<int, bool> find(int v) {
    bool p = P[v]; for (; UF[v] >= 0; p ^= P[v = UF[v]]);
    return make_pair(v, p);
  }
  void addEdge(int v, int w) {
    bool pv, pw; tie(v, pv) = find(v); tie(w, pw) = find(w); if (v == w) {
      history.emplace_back(v, w, 0, bipartiteGraph, B[v]);
      bipartiteGraph &= (B[v] = B[v] & (pv ^ pw)); return;
    }
    if (UF[v] > UF[w]) { swap(v, w); swap(pv, pw); }
    history.emplace_back(v, w, UF[w], P[w], B[v]);
    UF[v] += UF[w]; UF[w] = v; P[w] = pv ^ pw ^ 1; B[v] = B[v] & B[w]; cnt--;
  }
  void undo() {
    int v, w, ufw; bool pw, bv; tie(v, w, ufw, pw, bv) = history.back();
    history.pop_back(); B[v] = bv; if (ufw == 0) bipartiteGraph = pw;
    else { UF[w] = ufw; UF[v] -= UF[w]; P[w] = pw; cnt++; }
  }
  bool connected(int v, int w) { return find(v).first == find(w).first; }
  int getSize(int v) { return -UF[find(v).first]; }
  bool componentBipartite(int v) { return B[find(v).first]; }
  bool color(int v) { return find(v).second; }
  bool pathParity(int v, int w) { return color(v) ^ color(w); }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Supports queries for whether a graph component is bipartite
//   after edges have been added using Union Find by size with path compression
// Vertices are 0-indexed
//   V: the number of vertices in the graph
// Fields:
//   UF: a vector of integers representing the parent of each vertex in the
//     tree, or the negative of the size of the connected component if that
//     vertex is a root
//   P: a vector of booleans representing the parity of the path to the root
//     of that connected component
//   B: a vector of booleans representing whether the component rooted at the
//     vertex is bipartite for root vertices, undefined otherwise
//   cnt: the current number of connected components
//   bipartiteGraph: a boolean indicating whether the current graph is
//     bipartite or not
// Functions:
//   find(v): returns a pair containing the root of the connected component and
//     the parity of the path from the root to vertex v
//   addEdge(v, w): adds an edge between vertices v and w
//   connected(v, w): returns true if v and w are in the same
//     connected component, false otherwise
//   getSize(v): returns the size of the connected component containing
//     vertex v
//   componentBipartite(v): returns whether the connected component containing
//     vertex v is bipartite or not
//   color(v): returns the color of vertex v for one
//     possible coloring of the graph, assuming the component is bipartite
//   pathParity(v, w): return the parity of the path from
//     v to w (false if even number of edges, true if odd), assuming the
//     component is bipartite and v and w are connected
// Time Complexity:
//   constructor: O(V)
//   find, addEdge, connected, getSize, componentBipartite, color, pathParity:
//     O(alpha V) amortized, O(log V) worse case
// Memory Complexity: O(V)
// Tested:
//   Stress Tested
//   https://www.spoj.com/problems/BUGLIFE/
//   https://cses.fi/problemset/task/1668
//   https://tlx.toki.id/problems/troc-16/D
struct IncrementalBipartite {
  vector<int> UF; vector<bool> P, B; int cnt; bool bipartiteGraph;
  IncrementalBipartite(int V)
      : UF(V, -1), P(V, false), B(V, true), cnt(V), bipartiteGraph(true) {}
  pair<int, bool> find(int v) {
    bool p = P[v]; for (; UF[v] >= 0; p ^= P[v = UF[v]]) if (UF[UF[v]] >= 0) {
      p ^= P[UF[v]]; P[v] = P[v] ^ P[UF[v]]; UF[v] = UF[UF[v]];
    }
    return make_pair(v, p);
  }
  void addEdge(int v, int w) {
    bool pv, pw; tie(v, pv) = find(v); tie(w, pw) = find(w);
    if (v == w) { bipartiteGraph &= (B[v] = B[v] & (pv ^ pw)); return; }
    if (UF[v] > UF[w]) { swap(v, w); swap(pv, pw); }
    UF[v] += UF[w]; UF[w] = v; P[w] = pv ^ pw ^ 1; B[v] = B[v] & B[w]; cnt--;
  }
  bool connected(int v, int w) { return find(v).first == find(w).first; }
  int getSize(int v) { return -UF[find(v).first]; }
  bool componentBipartite(int v) { return B[find(v).first]; }
  bool color(int v) { return find(v).second; }
  bool pathParity(int v, int w) { return color(v) ^ color(w); }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Determines whether an undirected graph is bipartite, or whether it has
//   an odd cycle
// Vertices are 0-indexed
// Constructor Arguments:
//   G: a generic undirected graph structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the graph
// Fields:
//   bipartite: a boolean indicating whether the graph is bipartite or not
//   color: a vector of booleans for one possible bipartite coloring
//   oddCycle: a vector of the vertices in an odd cycle of the graph, empty
//     if the graph is bipartite
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O(V + E)
// Memory Complexity: O(V)
// Tested:
//   Stress Tested
//   https://www.spoj.com/problems/BUGLIFE/
//   https://cses.fi/problemset/task/1669
struct Bipartite {
  int V; bool bipartite; vector<bool> color; vector<int> oddCycle;
  template <class Graph> Bipartite(const Graph &G)
      : V(G.size()), bipartite(true), color(V, false) {
    vector<int> to(G.size(), -2), q(G.size()), stk(G.size()); int top = 0;
    for (int s = 0; s < V && bipartite; s++) if (to[s] == -2) {
      int front = 0, back = 0; to[q[back++] = s] = -1; while (front < back) {
        int v = q[front++]; for (int w : G[v]) {
          if (to[w] == -2) color[q[back++] = w] = !color[to[w] = v];
          else if (color[w] == color[v]) {
            bipartite = false; int x = v, y = w; while (x != y) {
              x = to[stk[top++] = x]; oddCycle.push_back(y); y = to[y];
            }
            stk[top++] = x; while (top > 0) oddCycle.push_back(stk[--top]);
            oddCycle.push_back(w); return;
          }
        }
      }
    }
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Computes the dominator tree rooted at a vertex
// A vertex dominates v another vertex w if all paths from the root to w must
//   pass through v
// A vertex v is an immediate dominator of w if v dominates w and no other
//   vertex dominates w
// Vertices are 0-indexed
// Constructor Arguments:
//   G: a generic directed graph structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the graph
// Fields:
//   idom: a vector of the immediate dominator of each vertex, or -1 if it
//     is not connected to the root, or is the root vertex
// In practice, has a small constant
// Time Complexity:
//   constructor: O(V + E log V)
// Memory Complexity: O(V + E)
// Tested:
//   https://judge.yosupo.jp/problem/dominatortree
struct DominatorTree {
  int V, ind; vector<int> idom, sdom, par, ord, U, UF, m;
  vector<vector<int>> bucket, H;
  int find(int v) {
    if (UF[v] == v) return v;
    int fv = find(UF[v]); if (sdom[m[v]] > sdom[m[UF[v]]]) m[v] = m[UF[v]];
    return UF[v] = fv;
  }
  int eval(int v) { find(v); return m[v]; }
  template <class Digraph> void dfs(const Digraph &G, int v) {
    ord[sdom[v] = ind++] = v;
    for (int w : G[v]) if (sdom[w] == -1) { par[w] = v; dfs(G, w); }
  }
  template <class Digraph> DominatorTree(const Digraph &G, int root)
      : V(G.size()), ind(0), idom(V, -1), sdom(V, -1), par(V, -1), ord(V, -1),
        U(V, -1), UF(V), m(V), bucket(V), H(V) {
    for (int v = 0; v < V; v++) {
      UF[v] = m[v] = v; for (int w : G[v]) H[w].push_back(v);
    }
    dfs(G, root); for (int i = ind - 1; i > 0; i--) {
      int w = ord[i]; for (int v : H[w]) if (sdom[v] >= 0)
        sdom[w] = min(sdom[w], sdom[eval(v)]);
      bucket[ord[sdom[w]]].push_back(w);
      for (int v : bucket[par[w]]) U[v] = eval(v);
      bucket[UF[w] = par[w]].clear();
    }
    for (int i = 1; i < ind; i++) {
      int w = ord[i], u = U[w];
      idom[w] = sdom[w] == sdom[u] ? sdom[w] : idom[u];
    }
    for (int i = 1; i < ind; i++) { int w = ord[i]; idom[w] = ord[idom[w]]; }
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Recursive helper function
template <const int MAXV, class F>
void maximalCliques(const vector<bitset<MAXV>> &matrix, F &f,
                    bitset<MAXV> P, bitset<MAXV> X, bitset<MAXV> R) {
  if (!P.any()) {
    if (!X.any()) f(R);
    return;
  }
  auto q = (P | X)._Find_first(); auto cands = P & ~matrix[q];
  for (int i = 0; i < int(matrix.size()); i++) if (cands[i]) {
    R[i] = 1;
    maximalCliques<MAXV, F>(matrix, f, P & matrix[i], X & matrix[i], R);
    R[i] = P[i] = 0; X[i] = 1;
  }
}

// Runs a callback on the maximal cliques in a graph
// A clique is maximal if any vertex added to it would result in a non-clique
// Vertices are 0-indexed
// Template Arguments:
//   MAXV: the maximum number of vertices in the graph
//   F: the type of the function f
// Function Arguments:
//   matrix: a matrix of bitsets representing the adjacency matrix of the
//     graph, must be symmetric
//   f(s): the function to run a callback on for each clique, where s is a
//     bitset representing which vertices are in the clique
// In practice, has a very small constant
// Time Complexity: O(3^(V / 3)), much faster in practice
// Memory Complexity: O(V^2 / 64)
// Tested:
//   https://open.kattis.com/problems/friends
template <const int MAXV, class F>
void maximalCliques(const vector<bitset<MAXV>> &matrix, F f) {
  maximalCliques<MAXV, F>(matrix, f, ~bitset<MAXV>(), bitset<MAXV>(),
                          bitset<MAXV>());
}


text:
#pragma once
#include <bits/stdc++.h>
#include "../components/StronglyConnectedComponents.h"
using namespace std;

// Solves the two satisfiability problem and provides all possible values
//   for each variable
// Given an implication graph, determine whether a consistent assignment exists
// Functions for created an implication graph can be seen in ImplicationGraph.h
// Variables are 0-indexed
// Template Arguments:
//   MAXN: the maximum number of variables
// Constructor Arguments:
//   G: the implication graph with N * 2 vertices for N variables with vertex
//       a * 2 + 1 representing the affirmative for variable a, and a * 2
//       representing the negative for variable a
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         which is a list of ints)
//       size() const: returns the number of vertices in the graph
// Fields:
//   scc: the SCC of the implication graph
//   possibilities: a vector of integers representing the possible values for
//     that variable; 0 if guaranteed to be false, 1 if guaranteed to be true,
//     2 otherwise
// In practice, has a very small constant
// Time Complexity:
//   constructor: O(N + M + MAXN M / 32) for M equations
// Memory Complexity: O(N + M + MAXN M / 32)
// Tested:
//   https://dmoj.ca/problem/wac1p5
template <const int MAXN> struct TwoSatExtended {
  vector<pair<int, int>> DAG; SCC scc; vector<bitset<MAXN * 2>> dp;
  vector<int> possibilities;
  template <class ImplicationGraph>
  TwoSatExtended(const ImplicationGraph &G) : DAG(), scc(G, DAG) {
    int N = G.size() / 2;
    for (int i = 0; i < N; i++) if (scc.id[i * 2] == scc.id[i * 2 + 1]) return;
    dp.resize(scc.components.size());
    for (int i = 0; i < int(dp.size()); i++) dp[i][i] = 1;
    for (auto &&e : DAG) dp[e.first] |= dp[e.second];
    possibilities.assign(N, 2); for (int i = 0; i < N; i++) {
      if (dp[scc.id[i * 2]][scc.id[i * 2 + 1]]) possibilities[i] = 1;
      if (dp[scc.id[i * 2 + 1]][scc.id[i * 2]]) possibilities[i] = 0;
    }
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Finds small minimum vertex covers
// Vertices are 0-indexed
// Constructor Arguments:
//   V: the number of vertices in the graph
//   e: a vector of pairs in the form (v, w) representing
//     an undirected edge in the simple graph (no self loops or parallel edges)
//     between vertices v and w
//   K: the maximum size of the minimum vertex cover to find
// Fields:
//   V: the number of vertices in the graph
//   E: the number of vertices in the graph
//   minCover: the size of a minimum vertex cover with at most K vertices, or
//     V if no such cover exists
//   inCover: a vector of booleans representing whether each vertex is in the
//     minimum vertex cover with at most K vertices or not
// In practice, has a very small constant
// Time Complexity:
//   constructor: O(E log E + 2^K KV)
// Memory Complexity: O(V + E)
// Tested:
//   https://dmoj.ca/problem/occ19g5
struct SmallMinVertexCover {
  vector<pair<int, int>> edges; int V, E, curE, minCover; vector<int> nxt;
  vector<bool> cur, inCover, temp; vector<pair<int, int>> history;
  vector<pair<int, int>> init(vector<pair<int, int>> e) {
    for (auto &&ei : e) if (ei.first > ei.second) swap(ei.first, ei.second);
    e.reserve(e.size() + 1); e.emplace_back(-1, -1); sort(e.begin(), e.end());
    e.erase(unique(e.begin(), e.end()), e.end()); return e;
  }
  void cover(int v) {
    inCover[v] = 1; for (int e = nxt[0], last = 0; e <= E; e = nxt[e])
      if (!cur[e] && (edges[e].first == v || edges[e].second == v)) {
        cur[e] = 1; curE--; nxt[last] = nxt[e]; history.emplace_back(e, last);
      } else last = e;
  }
  void uncover(int v, int revertSize) {
    inCover[v] = 0;
    for (; int(history.size()) > revertSize; history.pop_back()) {
      cur[nxt[history.back().second] = history.back().first] = 0; curE++;
    }
  }
  void solve(int K, int k) {
    if (k >= minCover) return;
    if (curE == 0) { minCover = k; temp = inCover; return; }
    if (curE > (K - k) * V) return;
    int v = -1, w = -1, curSize = history.size();
    for (int e = nxt[0]; e <= E; e = nxt[e])
      if (!cur[e]) { tie(v, w) = edges[e]; break; }
    cover(v); solve(K, k + 1); uncover(v, curSize);
    cover(w); solve(K, k + 1); uncover(w, curSize);
  }
  SmallMinVertexCover(int V, const vector<pair<int, int>> &e, int K)
      : edges(init(e)), V(V), E(edges.size() - 1), curE(E), minCover(V),
        nxt(E + 1), cur(E + 1, 0), inCover(V, 0), temp(V, 1) {
    iota(nxt.begin(), nxt.end(), 1); solve(K, 0); temp = inCover;
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Functions for generating an implication graph
// Each function runs a callback on the created edges
// N variables will require a graph with N * 2 vertices, with vertex
//   a * 2 + 1 representing the affirmative for variable a, and a * 2
//   representing the negative for variable a

// Adds an implication (a -> b) with affA indicating if a is the affirmative
//   (if true) or the negative (if false), and similarly with b
// Template Arguments:
//   F: the type of f
// Functions Arguments:
//   affA: whether a is affirmative
//   a: the first variable
//   affB: whether b is affirmative
//   b: the second variable
//   f(i, j): the function to run a callback on for the corresponding edge
//     created by the implication
template <class F> void addImpl(bool affA, int a, bool affB, int b, F f) {
  f(a * 2 + affA, b * 2 + affB);
}

// Adds a disjunction (a | b) with affA indicating if a is the affirmative
//   (if true) or the negative (if false), and similarly with b
// Template Arguments:
//   F: the type of f
// Functions Arguments:
//   affA: whether a is affirmative
//   a: the first variable
//   affB: whether b is affirmative
//   b: the second variable
//   f(i, j): the function to run a callback on for the corresponding edge
//     created by the disjunction
template <class F> void addOr(bool affA, int a, bool affB, int b, F f) {
  addImpl(!affA, a, affB, b, f); addImpl(!affB, b, affA, a, f);
}

// Sets the variable a to true
// Template Arguments:
//   F: the type of f
// Functions Arguments:
//   a: the variable
//   f(i, j): the function to run a callback on for the corresponding edge
//     created by setting this variable to true
template <class F> void setTrue(int a, F f) {
  addImpl(false, a, true, a, f);
}


text:
#pragma once
#include <bits/stdc++.h>
#include "../components/StronglyConnectedComponents.h"
using namespace std;

// Solves the two satisfiability problem
// Given an implication graph, determine whether a consistent assignment exists
// Functions for created an implication graph can be seen in ImplicationGraph.h
// Variables are 0-indexed
// Constructor Arguments:
//   G: the implication graph with N * 2 vertices for N variables with vertex
//       a * 2 + 1 representing the affirmative for variable a, and a * 2
//       representing the negative for variable a
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         which is a list of ints)
//       size() const: returns the number of vertices in the graph
// Fields:
//   scc: the SCC of the implication graph
//   x: a vector of booleans for one possible valid assignment, or empty if
//     no valid assignment exists
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O(N + M) for M equations
// Memory Complexity: O(N + M)
// Tested:
//   https://judge.yosupo.jp/problem/two_sat
//   https://codeforces.com/contest/1215/problem/F
//   https://codeforces.com/contest/780/problem/D
struct TwoSat {
  SCC scc; vector<bool> x;
  template <class ImplicationGraph>
  TwoSat(const ImplicationGraph &G) : scc(G) {
    assert(G.size() % 2 == 0); int N = G.size() / 2;
    for (int i = 0; i < N; i++) if (scc.id[i * 2] == scc.id[i * 2 + 1]) return;
    x.assign(N, false);
    for (int i = 0; i < N; i++) x[i] = scc.id[i * 2] > scc.id[i * 2 + 1];
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Modified from https://github.com/kth-competitive-programming/kactl/blob/master/content/graph/MaximumClique.h,
//   which itself is based on
//   https://gitlab.com/janezkonc/mcqd/blob/master/mcqd.h,
//   which has a GPL3 license
// Computes the clique with the maximum number of vertices in a graph
// Can be used to compute the maximum independent set by finding the maximum
//   clique on the complement graph, with the minimum vertex cover being any
//   vertex not in the maximum independent set
// Vertices are 0-indexed
// Constructor Arguments:
//   matrix: a vector of vectors of booleans representing the adjacency matrix
//     of the graph, must be symmetric
// Fields:
//   maximumClique: a vertex of vertices in the maximum clique
// In practice, has a very small constant
// Time Complexity: exponential, much faster in practice
// Memory Complexity: O(V^2)
// Tested:
//   https://dmoj.ca/problem/clique
//   https://judge.yosupo.jp/problem/maximum_independent_set
struct MaximumClique {
  static constexpr const double limit = 0.025;
  struct Vertex { int i, d; Vertex(int i) : i(i), d(0) {} };
  vector<vector<bool>> matrix; vector<vector<int>> C;
  vector<int> maximumClique, q, S, old; double pk;
  void init(vector<Vertex> &r) {
    for (auto &&v: r) v.d = 0;
    for (auto &&v : r) for (auto &&w : r) v.d += matrix[v.i][w.i];
    sort(r.begin(), r.end(), [&] (const Vertex &v, const Vertex &w) {
      return v.d > w.d;
    });
    int mxD = r[0].d;
    for (int i = 0; i < int(r.size()); i++) r[i].d = min(i, mxD) + 1;
  }
  void expand(vector<Vertex> &R, int lvl = 1) {
    S[lvl] += S[lvl - 1] - old[lvl]; old[lvl] = S[lvl - 1];
    while (!R.empty()) {
      if (int(q.size()) + R.back().d <= int(maximumClique.size())) return;
      q.push_back(R.back().i); vector<Vertex> T;
      for (auto &&v : R) if (matrix[R.back().i][v.i]) T.emplace_back(v.i);
      if (!T.empty()) {
        if (S[lvl]++ / ++pk < limit) init(T);
        int mnk = max(int(maximumClique.size()) - int(q.size()) + 1, 1);
        int j = 0, mxk = 1; C[1].clear(); C[2].clear(); for (auto &&v : T) {
          int k = 1;
          auto f = [&] (int i) { return matrix[v.i][i]; };
          while (any_of(C[k].begin(), C[k].end(), f)) k++;
          if (k > mxk) C[(mxk = k) + 1].clear();
          if (k < mnk) T[j++].i = v.i;
          C[k].push_back(v.i);
        }
        if (j > 0) T[j - 1].d = 0;
        for (int k = mnk; k <= mxk; k++)
          for (int i : C[k]) { T[j].i = i; T[j++].d = k; }
        expand(T, lvl + 1);
      } else if (q.size() > maximumClique.size()) maximumClique = q;
      q.pop_back(); R.pop_back();
    }
  }
  MaximumClique(const vector<vector<bool>> &matrix)
      : matrix(matrix), C(matrix.size() + 1), S(C.size()), old(S), pk(0) {
    vector<Vertex> V; V.reserve(matrix.size());
    for (int i = 0; i < int(matrix.size()); i++) V.emplace_back(i);
    init(V); expand(V);
  }
};