#include "collapse.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define N 100005
using namespace std;
typedef long long ll;

int n, m, Q, B, cnt;
map < pair<int,int>, int > mp;

int bid[N];
struct Ed {
	int u, v, l, r;
	bool operator< (const Ed &a) const { return v<a.v; }
};
vector <Ed> ex[N], vec[N];
struct Qry
{
	int tt, x, id;
	bool operator< (const Qry &a) const { return x<a.x; }
};
vector <Qry> qry[N];

int id[2][N], sz[2][N];

bool cmp (const Ed &a, const Ed &b) { return a.u<b.u; }

void add (Ed ed, int l, int r)
{
	if (bid[l]==bid[r]) {
		ex[bid[l]].push_back(ed);
		return;
	}
	ex[bid[l]].push_back(ed);
	ex[bid[r]].push_back(ed);
	for (int i=bid[l]+1; i<=bid[r]-1; i++) { vec[i].push_back(ed); }
}

int find (int x, int tg) { return (id[tg][x]==x ? x : (id[tg][x]=find(id[tg][x], tg))); }
void unite (int u, int v, int tg)
{
	int fau=find(u, tg), fav=find(v, tg);
	if (fau==fav) { return; }
	cnt++;
	if (sz[0][fau]<sz[0][fav]) { swap(fau, fav); }
	id[0][fav]=fau; sz[0][fau]+=sz[0][fav];
}

vi simulateCollapse (int nn, vi T, vi X, vi Y, vi W, vi P)
{
	n=nn; m=T.size(); Q=W.size();

	B=ceil(sqrt(m));
	for (int i=0; i<m; i++) { bid[i]=(i/B); }

	for (int t=0; t<m; t++) {
		if (X[t]>Y[t]) { swap(X[t], Y[t]); }
		if (T[t]==0) { mp[make_pair(X[t], Y[t])]=t; }
		if (T[t]==1) {
			int lst=mp[make_pair(X[t], Y[t])];
			add((Ed){ X[t], Y[t], lst, t-1 }, lst, t-1);
			mp[make_pair(X[t], Y[t])]=-1;
		}
	}
	for (int t=0; t<m; t++) {
		if (T[t]==0) {
			int lst=mp[make_pair(X[t], Y[t])];
			if (lst!=-1 && lst==t) {
				add((Ed){ X[t], Y[t], t, m-1 }, t, m-1);
			}
		}
	}
	for (int i=0; i<Q; i++) {
		qry[bid[W[i]]].push_back((Qry){ W[i], P[i], i });
	}

	vector <int> ans(Q);

	for (int t=0; t<=bid[m-1]; t++) {
		sort(qry[t].begin(), qry[t].end());
		sort(vec[t].begin(), vec[t].end());
		for (int i=0; i<n; i++) { id[0][i]=i; sz[0][i]=1; } cnt=0;

		for (int i=0, j=0; i<(int)qry[t].size(); i++) {
			Qry qq=qry[t][i];
			while (j<(int)vec[t].size() && vec[t][j].v<=qq.x) { unite(vec[t][j].u, vec[t][j].v, 0); j++; }
			int tmpcnt=cnt;
			for (int k=0; k<(int)ex[t].size(); k++) {
				Ed cur=ex[t][k];
				if (cur.l<=qq.tt && qq.tt<=cur.r && cur.v<=qq.x) {
					int u=find(cur.u, 0), v=find(cur.v, 0);
					if (u!=v) { id[1][u]=u; id[1][v]=v; }
				}
			}
			for (int k=0; k<(int)ex[t].size(); k++) {
				Ed cur=ex[t][k];
				if (cur.l<=qq.tt && qq.tt<=cur.r && cur.v<=qq.x) {
					int u=find(cur.u, 0), v=find(cur.v, 0);
					unite(u, v, 1);
				}
			}
			ans[qq.id]+=qq.x-cnt;
			cnt=tmpcnt;
		}
	}

	for (int t=0; t<=bid[m-1]; t++) {
		for (int i=0; i<n; i++) { id[0][i]=i; sz[0][i]=1; } cnt=0;

		sort(vec[t].begin(), vec[t].end(), cmp);

		for (int i=(int)qry[t].size()-1, j=(int)vec[t].size()-1; i>=0; i--) {
			Qry qq=qry[t][i];
			while (j>=0 && vec[t][j].u>qq.x) { unite(vec[t][j].u, vec[t][j].v, 0); j--; }
			int tmpcnt=cnt;
			for (int k=0; k<(int)ex[t].size(); k++) {
				Ed cur=ex[t][k];
				if (cur.l<=qq.tt && qq.tt<=cur.r && cur.u>qq.x) {
					int u=find(cur.u, 0), v=find(cur.v, 0);
					if (u!=v) { id[1][u]=u; id[1][v]=v; sz[1][u]=1; sz[1][v]=1; }
				}
			}
			for (int k=0; k<(int)ex[t].size(); k++) {
				Ed cur=ex[t][k];
				if (cur.l<=qq.tt && qq.tt<=cur.r && cur.u>qq.x) {
					int u=find(cur.u, 0), v=find(cur.v, 0);
					unite(u, v, 1);
				}
			}
			ans[qq.id]+=(n-qq.x)-cnt;
			cnt=tmpcnt;
		}
	}

	return ans;
}