#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int SQ = 1000;
struct Query { int t, x, y, p; };
int N, C, Q;
Query A[MAXN+10], B[MAXN+10], V[MAXN*2+10];
vector<int> ans;
struct UF
{
int par[MAXN+10], sz[MAXN+10];
vector<int> S;
void init()
{
int i, j;
S.clear();
for(i=1; i<=N; i++) par[i]=i, sz[i]=1;
}
int Find(int x) { return x==par[x] ? x : Find(par[x]); }
int Union(int x, int y)
{
x=Find(x); y=Find(y);
if(x==y) return 0;
if(sz[x]<sz[y]) swap(x, y);
sz[x]+=sz[y]; par[y]=x;
S.push_back(y);
return 1;
}
void restore()
{
int v=S.back(); S.pop_back();
sz[par[v]]-=sz[v];
par[v]=v;
}
}uf;
vector<int> simulateCollapse(int _N, vector<int> _T, vector<int> _X, vector<int> _Y, vector<int> _W, vector<int> _P)
{
int i, j, k, p, q;
N=_N; C=_T.size(); Q=_W.size(); ans.resize(Q, N);
for(i=0; i<C; i++) if(_X[i]>_Y[i]) swap(_X[i], _Y[i]);
for(i=0; i<C; i++) A[i+1]={_T[i], _X[i]+1, _Y[i]+1, i+1};
for(i=0; i<Q; i++) B[i+1]={-1, _P[i]+1, i, _W[i]+1};
for(i=1; i<=C; i++) V[i]=A[i];
for(i=1; i<=Q; i++) V[i+C]=B[i];
sort(V+1, V+C+Q+1, [&](const Query &p, const Query &q)
{
if(p.p!=q.p) return p.p<q.p;
else return p.t>q.t;
});
for(i=0; i<=(C+Q)/SQ; i++)
{
int l=max(1, i*SQ), r=min(C+Q, (i+1)*SQ-1);
set<pii> S;
vector<pii> E1, E2;
vector<int> query;
for(j=1; j<l; j++)
{
if(V[j].t==0) S.insert({V[j].x, V[j].y});
else if(V[j].t==1) S.erase({V[j].x, V[j].y});
}
for(j=l; j<=r; j++)
{
if(V[j].t==-1)
{
query.push_back(j);
}
else
{
if(S.count({V[j].x, V[j].y}))
{
S.erase({V[j].x, V[j].y});
E2.push_back({V[j].x, V[j].y});
}
}
}
for(auto it : S) E1.push_back(it);
sort(E1.begin(), E1.end(), [&](const pii &p, const pii &q) { return p.second<q.second; });
sort(E2.begin(), E2.end(), [&](const pii &p, const pii &q) { return p.second<q.second; });
sort(query.begin(), query.end(), [&](const int &p, const int &q) { return V[p].x<V[q].x; });
uf.init(); j=0;
for(auto &it : query)
{
for(; j<E1.size() && E1[j].second<=V[it].x; j++) uf.Union(E1[j].first, E1[j].second);
set<pii> S1, S2;
for(p=l; p<=it; p++)
{
if(V[p].t==-1) continue;
if(V[p].y>V[it].x) continue;
if(V[p].t==0) S1.insert({V[p].x, V[p].y});
else S1.erase({V[p].x, V[p].y});
S2.insert({V[p].x, V[p].y});
}
int cnt=0;
for(auto jt : S1) cnt+=uf.Union(jt.first, jt.second);
for(auto jt : E2) if(jt.second<=V[it].x && !S2.count(jt)) cnt+=uf.Union(jt.first, jt.second);
ans[V[it].y]-=uf.S.size();
while(cnt--) uf.restore();
}
sort(E1.begin(), E1.end(), [&](const pii &p, const pii &q) { return p.first>q.first; });
sort(E2.begin(), E2.end(), [&](const pii &p, const pii &q) { return p.first>q.first; });
sort(query.begin(), query.end(), [&](const int &p, const int &q) { return V[p].x>V[q].x; });
uf.init(); j=0;
for(auto &it : query)
{
for(; j<E1.size() && E1[j].first>V[it].x; j++) uf.Union(E1[j].first, E1[j].second);
set<pii> S1, S2;
for(p=l; p<=it; p++)
{
if(V[p].t==-1) continue;
if(V[p].x<=V[it].x) continue;
if(V[p].t==0) S1.insert({V[p].x, V[p].y});
else S1.erase({V[p].x, V[p].y});
S2.insert({V[p].x, V[p].y});
}
int cnt=0;
for(auto jt : S1) cnt+=uf.Union(jt.first, jt.second);
for(auto jt : E2) if(jt.first>V[it].x && !S2.count(jt)) cnt+=uf.Union(jt.first, jt.second);
ans[V[it].y]-=uf.S.size();
while(cnt--) uf.restore();
}
}
return ans;
}
