# include "collapse.h"
# include <bits/stdc++.h>
using namespace std;
int U[100010],V[100010],lc[200010],rc[200010],tot=0;
vector<int> ans;
map<pair<int,int>,int> mp;
forward_list<int> edge[200010];
struct Update
{
	int x1,x2,y1,y2,id;
	Update(){}
	Update(int x1,int x2,int y1,int y2,int i):x1(x1),x2(x2),y1(y1),y2(y2),id(i){}
}upd[200010];
struct Query
{
	int x,y,id;
	Query(){}
	Query(int x,int y,int i):x(x),y(y),id(i){}
}qry[100010];
struct Node
{
	int x1,x2,y1,y2;
	Node(){}
	Node(int x1,int x2,int y1,int y2):x1(x1),x2(x2),y1(y1),y2(y2){}
	inline Node operator+(const Node &t)const
	{
		return Node(min(x1,t.x1),max(x2,t.x2),min(y1,t.y1),max(y2,t.y2));
	}
}tr[200010];
namespace DSU
{
	int cnt,fa[100010],rnk[100010],tp=0;
	pair<int,int> upd[20000010];
	void init(int n){cnt=n;iota(fa,fa+n,0);}
	int getF(int u){return u==fa[u]?u:getF(fa[u]);}
	void merge(int u,int v)
	{
		u=getF(u);v=getF(v);
		if(u==v) return;
		cnt--;
		if(rnk[u]>rnk[v]) swap(u,v);
		upd[++tp]={u,rnk[u]==rnk[v]};
		fa[u]=v;rnk[v]=max(rnk[u]+1,rnk[v]);
	}
	void undo(int ttp)
	{
		for(;tp>ttp;tp--)
		{
			int u=upd[tp].first,v=upd[tp].second;
			cnt++;fa[u]=u;
			if(v) rnk[v]=rnk[u];
		}
	}
}
int build(int l,int r,int d)
{
	if(l==r) return tr[++tot]=Node(qry[l].x,qry[l].x,qry[l].y,qry[l].y),tot;
	int rt=++tot,mid=(l+r)/2;
	if(d) nth_element(qry+l,qry+mid,qry+r+1,[](const auto &a,const auto &b){return a.x<b.x;});
	else nth_element(qry+l,qry+mid,qry+r+1,[](const auto &a,const auto &b){return a.y<b.y;});
	lc[rt]=build(l,mid,d^1);
	rc[rt]=build(mid+1,r,d^1);
	tr[rt]=tr[lc[rt]]+tr[rc[rt]];
	return rt;
}
void update(int rt,Update &x)
{
	if(tr[rt].x1>x.x2 || tr[rt].x2<x.x1 || tr[rt].y1>x.y2 || tr[rt].y2<x.y1) return;
	if(tr[rt].x1>=x.x1 && tr[rt].x2<=x.x2 && tr[rt].y1>=x.y1 && tr[rt].y2<=x.y2) return assert(++tot<=20000000),edge[rt].push_front(x.id),void();
	update(lc[rt],x);update(rc[rt],x);
}
void slv(int rt,int l,int r)
{
	int ttp=DSU::tp;
	for(int i:edge[rt]) DSU::merge(U[i],V[i]);
	if(l==r) ans[qry[l].id]=DSU::cnt;
	else
	{
		int mid=(l+r)/2;
		slv(lc[rt],l,mid);
		slv(rc[rt],mid+1,r);
	}
	DSU::undo(ttp);
}
vector<int> simulateCollapse(int n,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P)
{
	int N=T.size(),m=0,q=W.size();
	ans.resize(q);
	for(int i=0;i<N;i++)
	{
		if(X[i]>Y[i]) swap(X[i],Y[i]);
		U[i]=X[i];V[i]=Y[i];
		if(T[i]==0) mp[{X[i],Y[i]}]=i;
		else
		{
			int le=mp[{X[i],Y[i]}];
			mp.erase({X[i],Y[i]});
			if(X[i]) upd[++m]=Update(le,i-1,0,X[i]-1,le);
			if(Y[i]<=n-2) upd[++m]=Update(le,i-1,Y[i],n-2,le);
		}
	}
	for(auto p:mp)
	{
		int u=p.first.first,v=p.first.second,le=p.second;
		if(u) upd[++m]=Update(le,N-1,0,u-1,le);
		if(v<=n-2) upd[++m]=Update(le,N-1,v,n-2,le);
	}
	for(int i=0;i<q;i++) qry[i]=Query(W[i],P[i],i);
	int rt=build(0,q-1,0);
	tot=0;
	for(int i=1;i<=m;i++) update(rt,upd[i]);
	DSU::init(n);
	slv(rt,0,q-1);
	return ans;
}