#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
const int S=317;
struct DSU
{
int p[N],z[N],n,cmp,S[N],c;
void init(int _n){ n=_n;for(int i=1;i<=n;i++) p[i]=i,z[i]=1;cmp=n;c=0;}
DSU(){}
int Find(int x){ return p[x]==x?x:Find(p[x]);}
void Union(int x, int y, bool bck)
{
x=Find(x);y=Find(y);
if(x==y){ if(bck) S[++c]=0;return;}
cmp--;
if(z[x]>z[y]) swap(x,y);
p[x]=y;
z[y]+=z[x];
S[++c]=x;
}
void Undo()
{
if(!S[c]) c--;
else
{
cmp++;
int x=S[c--];
z[p[x]]-=z[x];
p[x]=x;
}
}
} DS;
int n,m,q;
int t[N],x[N],y[N],rng[N],w[N],p[N],ans[N];
map<pair<int,int>,int> last;
vector<int> Qs[N];
vector<int> Solve()
{
for(int i=1;i<=m;i++)
{
if(t[i]==0) rng[i]=m,last[{x[i],y[i]}]=i;
else rng[last[{x[i],y[i]}]]=i-1;
}
for(int l=1;l<=m;l+=S)
{
int r=min(m,l+S-1);
vector<int> add,now;
for(int i=1;i<=r;i++)
{
if(t[i]==1 || rng[i]<l) continue;
if(rng[i]<=r || i>=l) add.pb(i);
else now.pb(i);
}
vector<int> qs;
for(int i=l;i<=r;i++) for(int Q:Qs[i]) qs.pb(Q);
sort(now.begin(),now.end(),[&](int i, int j){ return y[i]<y[j];});
sort(qs.begin(),qs.end(),[&](int i, int j){ return p[i]<p[j];});
int e_ptr=0,q_ptr=0;
DS.init(n);
for(int i=1;i<=n;i++)
{
while(e_ptr<now.size() && y[now[e_ptr]]==i) DS.Union(x[now[e_ptr]],y[now[e_ptr]],0),e_ptr++;
while(q_ptr<qs.size() && p[qs[q_ptr]]==i)
{
int qid=qs[q_ptr];
int cnt=0;
for(int e:add) if(w[qid]>=e && w[qid]<=rng[e] && y[e]<=p[qid]) DS.Union(x[e],y[e],1),cnt++;
ans[qid]+=DS.cmp-(n-i);
while(cnt--) DS.Undo();
q_ptr++;
}
}
sort(now.begin(),now.end(),[&](int i, int j){ return x[i]>x[j];});
reverse(qs.begin(),qs.end());
e_ptr=q_ptr=0;
DS.init(n);
for(int i=n;i>=1;i--)
{
while(e_ptr<now.size() && x[now[e_ptr]]==i) DS.Union(x[now[e_ptr]],y[now[e_ptr]],0),e_ptr++;
while(q_ptr<qs.size() && p[qs[q_ptr]]==i-1)
{
int qid=qs[q_ptr];
int cnt=0;
for(int e:add) if(w[qid]>=e && w[qid]<=rng[e] && x[e]>p[qid]) DS.Union(x[e],y[e],1),cnt++;
ans[qid]+=DS.cmp-p[qid];
while(cnt--) DS.Undo();
q_ptr++;
}
}
}
vector<int> ret;
for(int i=1;i<=q;i++) ret.pb(ans[i]);
return ret;
}
vector<int> simulateCollapse(int _n, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P)
{
n=_n;m=X.size();q=W.size();
for(int i=1;i<=m;i++) t[i]=T[i-1],x[i]=X[i-1]+1,y[i]=Y[i-1]+1;
for(int i=1;i<=q;i++) w[i]=W[i-1]+1,p[i]=P[i-1]+1,Qs[w[i]].pb(i);
for(int i=1;i<=m;i++) if(x[i]>y[i]) swap(x[i],y[i]);
return Solve();
}
