#include "collapse.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second

const int K = 500;

struct dsu {
	int n, cmp;
	vector<int> par, siz;
	dsu() = default;
	dsu(int n_) {
		cmp = 0;
		n = n_;
		par.assign(n, 0);
		iota(all(par), 0);
		siz.assign(n, 1);
	}

	int get(int v) {
		return (par[v] == v ? v : par[v] = get(par[v]));
	}

	void merge(int u, int v) {
		u = get(u);
		v = get(v);
		if (u == v) return;
		cmp--;
		if (siz[v] > siz[u]) swap(u, v);
		par[v] = u;
		siz[u] += siz[v];
	}
};		

std::vector<int> simulateCollapse(
	int N,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P
) {
	int n = N;
	int c = sz(X);
	vector<vector<pair<int, int>>> qrs(c);
	for (int i = 0; i < sz(W); i++) {
		qrs[W[i]].pb({P[i], i});
	}
	vector<int> ans(sz(W));
	vector<vector<int>> gr(n);
	vector<int> used1(n), used_dfs(n);
	int step = 0;
	for(int i = 0; i < c; i++){
		if(X[i]>Y[i])swap(X[i],Y[i]);
	}
	vector<int> prev(c, -1);
	unordered_map<ll, int> lpos;
	for (int i = 0; i < c; i++) {
		if (lpos.find(X[i] * 1ll * n + Y[i]) != lpos.end()) prev[i] = lpos[X[i] * 1ll * n + Y[i]];
		prev[X[i] * 1ll * n + Y[i]] = i;
	}
	vector<int> USED(n, 0);
	for (int i = 0; i < c; i += K) {
		unordered_set<ll> ch_edg;
		unordered_set<ll> LOL;
		for (int j = i; j < min(c, i + K); j++) {
			if (T[j] == 0) {
				USED[j] = 1;
			} else if (prev[j] != -1) USED[prev[j]] = 0;
			if (T[j] == 1 && ch_edg.find(X[j] * 1ll * N + Y[j]) == ch_edg.end()) {
				LOL.insert(X[j] * 1ll * n + Y[j]);
			}
			ch_edg.insert(X[j] * 1ll * N + Y[j]);
		}
		vector<vector<int>> by_rig(n), by_left(n);
		for (int j = i - 1; j >= 0; j--) {
			if (USED[j]) {
				by_rig[max(X[j], Y[j])].pb(min(X[j], Y[j]));
				by_left[min(X[j], Y[j])].pb(max(X[j], Y[j]));
			}
		}
		vector<vector<pair<int, int>>> qnums(n - 1);
		for (int j = i; j < min(c, i + K); j++) {
			for (auto &[el, num] : qrs[j]) {
				qnums[el].pb({j, num});
			}
		}
		dsu d(n);
		for (int I = 0; I < n - 1; I++) {
			d.cmp++;
			for (auto &u : by_rig[I]) d.merge(u, I);
			for (auto &[time, numb] : qnums[I]) {
				step++;
				unordered_set<ll> add_edges = LOL;
				for (int j = i; j <= time; j++) {
					if (T[j] == 0) {
						add_edges.insert(X[j] * 1ll * n + Y[j]);
					} else {
						add_edges.erase(X[j] * 1ll * n + Y[j]);
					}
				}
				vector<int> rdfs;
				for (auto E : add_edges) {
					ll u = E / n, v = E % n;
					if (max(u, v) <= I) {
						u = d.get(u);
						v = d.get(v);
						if (u != v) {
							if (used1[u] != step) gr[u].clear();
							if (used1[v] != step) gr[v].clear();
							used1[u] = step;
							used1[v] = step;
							gr[u].pb(v);
							gr[v].pb(u);
							rdfs.pb(u);
						}
					}
				}
				int ccmp = d.cmp;
				auto dfs = [&](int v, auto&&dfs) -> void {
					used_dfs[v] = step;
					for (auto &u : gr[v]) {
						if (used_dfs[u] != step) {
							ccmp--;
							dfs(u, dfs);
						}
					}
				};
				for (auto &u : rdfs) {
					if (used_dfs[u] != step) {
						dfs(u, dfs);
					}
				}
				ans[numb] += ccmp;
			}
		}
		iota(all(d.par), 0);
		d.siz.assign(n, 1);
		d.cmp = 0;
		for (int I = n - 1; I >= 1; I--) {
			d.cmp++;
			for (auto &u : by_left[I]) d.merge(u, I);
			for (auto &[time, numb] : qnums[I - 1]) {
				step++;
				unordered_set<ll> add_edges = LOL;
				for (int j = i; j <= time; j++) {
					if (T[j] == 0) {
						add_edges.insert(X[j] * 1ll * n + Y[j]);
					} else {
						add_edges.erase(X[j] * 1ll * n + Y[j]);
					}
				}
				vector<int> rdfs;
				for (auto E : add_edges) {
					int u = E / n, v = E % n;
					if (min(u, v) >= I) {
						u = d.get(u);
						v = d.get(v);
						if (u != v) {
							if (used1[u] != step) gr[u].clear();
							if (used1[v] != step) gr[v].clear();
							used1[u] = step;
							used1[v] = step;
							gr[u].pb(v);
							gr[v].pb(u);
							rdfs.pb(u);
						}
					}
				}
				int ccmp = d.cmp;
				auto dfs = [&](int v, auto&&dfs) -> void {
					used_dfs[v] = step;
					for (auto &u : gr[v]) {
						if (used_dfs[u] != step) {
							ccmp--;
							dfs(u, dfs);
						}
					}
				};
				for (auto &u : rdfs) {
					if (used_dfs[u] != step) {
						dfs(u, dfs);
					}
				}
				ans[numb] += ccmp;
			}
		}
	}
	return ans;
}