#include "collapse.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
constexpr int B = 1001;
struct DSU{
int path[100100], sz[100100], cnt;
vector<pair<int, int>> mylog;
void init(int n){for (int i=1;i<=n;i++){path[i] = i; sz[i] = 1;} mylog.clear(); cnt = 0;}
int find(int s){
if (s==path[s]) return s;
return find(path[s]);
}
bool merge(int x, int y){
//printf("merge: %d %d\n", x, y);
x = find(x), y = find(y);
if (x==y) return 0;
cnt++;
if (sz[x] > sz[y]) swap(x, y);
path[x] = y;
sz[y] += sz[x];
mylog.emplace_back(x, sz[x]);
return 1;
}
void rollback(int c){
while(c--){
auto [x, _sz] = mylog.back(); mylog.pop_back();
sz[path[x]] -= _sz;
path[x] = x;
--cnt;
}
}
int count(int x){return x - cnt;}
}dsu;
struct Edge{
int x, y;
Edge(){}
Edge(int _x, int _y): x(_x), y(_y) {}
}E[200200];
struct Query{
int w, p, i;
Query(){}
Query(int _w, int _p, int _i): w(_w), p(_p), i(_i) {}
};
vector<Query> bucket[110000];
map<int, int> mp[110000];
int idx[110000], updated[110000], on[110000], ans[110000];
bool cmpB(const Query &x, const Query &y){return x.p < y.p;}
bool cmpE(int x, int y){return E[x].y < E[y].y;}
void calc(int n, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P){
int c = T.size(), q = W.size();
///init
for (int i=1;i<=c;i++){
mp[i].clear();
on[i] = 0;
updated[i] = 0;
}
for (int i=0;i<=c/B;i++) bucket[i].clear();
fill(E, E+c+1, Edge(0, 0));
///
int Ecnt = 0;
for (int i=1;i<=c;i++){
int op, x, y;
op = T[i-1], x = X[i-1], y = Y[i-1];
if (x==y) {idx[i] = 0; continue;}
if (x > y) swap(x, y);
if (mp[x].find(y)==mp[x].end()){
mp[x][y] = ++Ecnt;
E[Ecnt] = Edge(x, y);
}
idx[i] = mp[x][y];
}
for (int i=1;i<=q;i++){
int w, p;
w = W[i-1], p = P[i-1];
bucket[w/B].emplace_back(w, p, i);
}
vector<int> onE;
for (int z=0;z<=c/B;z++){
int l = z*B, r = (z+1)*B;
for (int i=l;i<r;i++) if (idx[i]) updated[idx[i]] = 1;
sort(bucket[z].begin(), bucket[z].end(), cmpB);
dsu.init(n);
int pt = 0;
for (auto &[w, p, qi]:bucket[z]){
while(pt < (int)onE.size() && E[onE[pt]].y <= p){
if (!updated[onE[pt]]) dsu.merge(E[onE[pt]].x, E[onE[pt]].y);
pt++;
}
for (int i=l;i<=w;i++) if (idx[i]) on[idx[i]] ^= 1;
int cnt = 0;
for (int i=l;i<r;i++) if (idx[i] && on[idx[i]] && E[idx[i]].y <= p){
if (dsu.merge(E[idx[i]].x, E[idx[i]].y)) cnt++;
}
//printf("ok %d -> %d\n", qi, dsu.count(p));
ans[qi] += dsu.count(p);
dsu.rollback(cnt);
for (int i=l;i<=w;i++) if (idx[i]) on[idx[i]] ^= 1;
}
for (int i=l;i<r;i++) if (idx[i]) on[idx[i]] ^= 1, updated[idx[i]] = 0;
vector<int> nE;
for (auto &x:onE) if (on[x]) nE.push_back(x);
for (int i=l;i<r;i++) if (on[idx[i]]) nE.push_back(idx[i]);
sort(nE.begin(), nE.end(), cmpE);
nE.erase(unique(nE.begin(), nE.end()), nE.end());
swap(nE, onE);
}
}
std::vector<int> simulateCollapse(
int N,
std::vector<int> T,
std::vector<int> X,
std::vector<int> Y,
std::vector<int> W,
std::vector<int> P
) {
for (auto &x:X) ++x;
for (auto &x:Y) ++x;
for (auto &x:W) ++x;
for (auto &x:P) ++x;
calc(N, T, X, Y, W, P);
for (auto &x:X) x = N+1 - x;
for (auto &y:Y) y = N+1 - y;
for (auto &p:P) p = N - p;
calc(N, T, X, Y, W, P);
vector<int> ret(W.size());
for (int i=0;i<(int)W.size();i++) ret[i] = ans[i+1];
return ret;
}
