//S2
#include "collapse.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1e5 + 5;
class dsu_type{
public:
int n, com;
int head[maxn], sz[maxn];
stack<pii> stk;
int findhead(int x) {
if(x==head[x]) return x;
return findhead(head[x]);
}
void init(int _n) {
n = com = _n;
for(int i=0;i<n;i++) {
head[i] = i;
sz[i] = 1;
}
while(!stk.empty()) stk.pop();
}
void add_edge(int u, int v) {
int x = findhead(u), y = findhead(v);
if(sz[x] > sz[y]) swap(x,y);
stk.push({x,y});
if(x!=y) {
head[x] = y;
sz[y] += sz[x];
com--;
}
}
void pop_edge() {
int x = stk.top().X, y = stk.top().Y; stk.pop();
if(x!=y) {
head[x] = x;
sz[y] -= sz[x];
com++;
}
}
int getcom() {
return com;
}
} dsu;
struct node {
int u,v,l,r;
node(int _u = 0, int _v = 0, int _l = 0, int _r = 0) {
u = _u; v = _v; l = _l; r = _r;
}
};
int n,m,q;
map<pii,int> pos;
vector<node> itv;
vector<pii> ask[maxn];
vector<pii> edge[maxn*4];
int res[maxn];
void update(int pos, int l, int r, int x, int y, pii val) {
if(l>r || r<x || y<l) return ;
if(x<=l && r<=y) {
// printf("edge %d [%d, %d] : %d %d\n",pos,l,r,val.X,val.Y);
edge[pos].push_back(val);
return ;
}
int mid = (l+r)/2;
update(pos<<1,l,mid,x,y,val);
update(pos<<1|1,mid+1,r,x,y,val);
}
void solve(int pos, int l, int r) {
for(auto t : edge[pos]) dsu.add_edge(t.X,t.Y);
if(l==r) {
// printf("res %d = %d\n",l,dsu.getcom());
for(auto t : ask[l]) res[t.Y] = dsu.getcom();
}
else {
int mid = (l+r)/2;
solve(pos<<1,l,mid);
solve(pos<<1|1,mid+1,r);
}
int tmp = edge[pos].size();
for(int i=0;i<tmp;i++) dsu.pop_edge();
// printf("end %d, %d : pop %d\n",l,r,tmp);
}
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
) {
n = N; m = T.size(); q = W.size();
for(int i=0;i<m;i++) {
int u = X[i], v = Y[i];
if(u>v) swap(u,v);
if(u<=P[0] && P[0]+1<=v) continue;
if(T[i]==0) pos[{u,v}] = i;
else {
itv.push_back(node(u,v,pos[{u,v}],i-1));
pos[{u,v}] = -1;
}
}
for(auto t : pos) {
if(t.Y==-1) continue;
itv.push_back(node(t.X.X,t.X.Y,t.Y,m-1));
}
// for(auto t : itv) printf("itv %d %d %d %d\n",t.l,t.r,t.u,t.v);
for(int i=0;i<q;i++) {
ask[W[i]].push_back({P[i],i});
}
dsu.init(n);
for(auto t : itv) update(1,0,m-1,t.l,t.r,{t.u,t.v});
solve(1,0,m-1);
vector<int> vec;
for(int i=0;i<q;i++) vec.push_back(res[i]);
return vec;
}
