#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=(1LL<<17);
const ld pi=acos(-1);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
vector<ll> ret;
struct TSG{
ll n;
ll dir[N],sz[N],stk[N],now;
void init(ll _n){
n=_n;
REP1(i,n)dir[i]=i,sz[i]=1;
now=0;
}
//dsu
ll find(ll id){
while(dir[id]!=id)id=dir[id];
return id;
}
void uni(ll x,ll y){
x=find(x);y=find(y);
if(x==y){return ;}
if(sz[x]>sz[y])swap(x,y);
stk[++now]=x;
dir[x]=y;
sz[y]+=sz[x];
}
void undo(){
sz[dir[stk[now]]]-=sz[stk[now]];
dir[stk[now]]=stk[now];
--now;
}
//append or delete operations
vector<pll> opr[4*N];
void _app(ll id,ll l,ll r,ll ql,ll qr,pll o){
if(l>=ql&&r<=qr){opr[id].pb(o);return ;}
if(l>=qr||r<=ql)return ;
ll mid=(l+r)>>1;
_app(id*2,l,mid,ql,qr,o);
_app(id*2+1,mid,r,ql,qr,o);
}
void app(ll ql,ll qr,pll o){_app(1,1,n+1,ql,qr,o);return ;}
void _del(ll id,ll l,ll r,ll ql,ll qr){
if(l>=ql&&r<=qr){opr[id].resize(SZ(opr[id])-1);return ;}
if(l>=qr||r<=ql)return ;
ll mid=(l+r)>>1;
_del(id*2,l,mid,ql,qr);
_del(id*2+1,mid,r,ql,qr);
}
void del(ll ql,ll qr){_del(1,1,n+1,ql,qr);return ;}
//locations of query
vector<ll> qid[N];
ll seg[4*N];
void _ins(ll id,ll l,ll r,ll to,ll ip){
if(l==r-1){qid[l].pb(ip);seg[id]=SZ(qid[l]);return ;}
ll mid=(l+r)>>1;
if(to<mid){
_ins(id*2,l,mid,to,ip);
}else{
_ins(id*2+1,mid,r,to,ip);
}
seg[id]=seg[id*2]+seg[id*2+1];
}
void ins(ll to,ll ip){_ins(1,1,n+1,to,ip);return ;}
//answer
void build(ll id,ll l,ll r){
ll st=now;
for(pll i:opr[id])uni(i.X,i.Y);
if(l==r-1){
for(ll i:qid[l])ret[i]=n-now;
qid[l].clear();
seg[id]=0;
}
if(l<r-1){
ll mid=(l+r)>>1;
if(seg[id*2])build(id*2,l,mid);
if(seg[id*2+1])build(id*2+1,mid,r);
seg[id]=seg[id*2]+seg[id*2+1];
}
while(now>st)undo();
}
}S;
vector<pll> opr[4*N],query[N];
ll sum[4*N];
void add(ll id,ll l,ll r,ll ql,ll qr,pll o){
if(l>=ql&&r<=qr){opr[id].pb(o);return ;}
if(l>=qr||r<=ql)return ;
ll mid=(l+r)>>1;
add(id*2,l,mid,ql,qr,o);
add(id*2+1,mid,r,ql,qr,o);
}
void ins(ll id,ll l,ll r,ll to){
if(l==r-1){++sum[id];return ;}
ll mid=(l+r)>>1;
if(to<mid){
ins(id*2,l,mid,to);
}else{
ins(id*2+1,mid,r,to);
}
sum[id]=sum[id*2]+sum[id*2+1];
}
void build(ll id,ll l,ll r){
for(auto i:opr[id]){
S.app(0,i.X,i);
S.app(i.Y,S.n+1,i);
}
if(l==r-1){
for(auto i:query[l])S.ins(i.X,i.Y);
if(SZ(query[l]))S.build(1,1,S.n+1);
}else{
ll mid=(l+r)>>1;
if(sum[id*2])build(id*2,l,mid);
if(sum[id*2+1])build(id*2+1,mid,r);
}
for(auto i:opr[id]){
S.del(0,i.X);
S.del(i.Y,S.n+1);
}
}
ll n,q,c;
map<pll,ll> lst;
vector<ll> simulateCollapse(ll _N,vector<ll> ty,vector<ll> x,vector<ll> y,vector<ll> w,vector<ll> p){
n=_N;q=SZ(w);c=SZ(ty);
ret.resize(q);S.init(n);
REP(i,c){
++x[i];++y[i];
if(x[i]>y[i])swap(x[i],y[i]);
if(ty[i]==0){
lst[mp(x[i],y[i])]=i;
}else{
auto it=lst.find(mp(x[i],y[i]));
add(1,0,c+1,lst[mp(x[i],y[i])],i,mp(x[i],y[i]));
lst.erase(it);
}
}
for(auto i:lst){add(1,0,c+1,i.Y,c,i.X);}
REP(i,q){
++p[i];
ins(1,0,c+1,w[i]);
query[w[i]].pb(mp(p[i],i));
}
build(1,0,c+1);
return ret;
}
/*
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
vector<ll> T={0,0,0,0};
vector<ll> TX={0,1,2,4};
vector<ll> TY={1,3,4,0};
vector<ll> W={3};
vector<ll> P={1};
vector<ll> ans=simulateCollapse(5,T,TX,TY,W,P);
for(auto i:ans)cout<<i<<"\n";
return 0;
}
//*/
