线段树分治

const int N = ${1:this};
int ans[N];

struct DSU {
  struct Info {
    int u, v, add;
  };
  vector<int> p, h;
  vector<Info> st;
  int idx = 0;
    DSU(int n) {
      p.resize(n + 1);
      h.resize(n + 1);
      iota(p.begin(), p.end(), 0);
    }

    int find(int x){
      while (x != p[x]) {
        x = p[x];
      }
        return p[x];
    }

    void merge(int u, int v){
        int fu = find(u);
        int fv = find(v);
        if (fu == fv){
            return;
        }
        if (h[fu] > h[fv]){
            swap(fu, fv);
        }
        st.emplace_back(fu, fv, h[fu] == h[fv]);
        idx++;
        p[fu] = fv;
        if (h[fu] == h[fv]) {
          h[fv]++;
        }
    }

    void restore(int t){ // 回溯到 t 时刻
        while (st.size() > t){
          resume();
        }
    }

    void resume() {
      auto [u, v, add] = st.back();
      h[p[u]] -= add;
      p[u] = u;
        st.pop_back();
        idx--;
  }
} dsu(N);
// 这里取决于维护的点数！

template<class Info, class Tag>
struct SegmentTree {
  vector<Info> info;
  int n;
  SegmentTree() : n(0) { }
  SegmentTree(int n_) {
    n = n_;
    info.assign(4 << __lg(n), Info());
  }
  void init(int n_) {
    n = n_;
    info.assign(4 << __lg(n), Info());
  }
  void apply(int p, const Tag &v) {
    info[p].apply(v);
  }
  void range_apply(int p, int l, int r, int x, int y, const Tag &v) {
    if (l > y || r < x) {
      return;
    }
    if (l >= x && r <= y) {
      apply(p, v);
      return;
    }
    int mid = l + r >> 1;
    range_apply(p << 1, l, mid, x, y, v);
    range_apply(p << 1 | 1, mid + 1, r, x, y, v);
  }
  void range_apply(int l, int r, const Tag &v) {
    return range_apply(1, 1, n, l, r, v);
  }
  void range_query(int p, int l, int r) {

    int pre = dsu.idx;

    for (auto [u, v] : info[p].edge) {

    }

    // 记得不能随意 return，只要更改了，返回之前必须撤销！！！

    if (l == r) {

    } else {
      int mid = l + r >> 1;
      range_query(p << 1, l, mid);
      range_query(p << 1 | 1, mid + 1, r);
    }

    dsu.restore(pre);
  }
};

struct Tag {
  int u, v;
  Tag(int u, int v) : u(u), v(v) { }
};

struct Info {
  vector<pair<int, int>> edge;
  Info() {
    edge.clear();
  }
  void apply(const Tag &v) {
    edge.emplace_back(v.u, v.v);
  }
};