#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int N = 5e5;
const int K = 205;
struct dsu{
vector<int> sz, p;
vector<pair<int&, int>> hist;
vector<int> sizes;
int n, cc, cc1;
void init(int ns){
n = ns;
sz.resize(n + 1);
p.resize(n + 1);
for (int i = 1; i <= n; i++){
sz[i] = 1;
p[i] = i;
}
cc = n;
cc1 = 0;
}
int get(int v){
return (v == p[v]) ? v : get(p[v]);
}
void unite(int x, int y){
x = get(x); y = get(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
hist.pb({p[x], p[x]});
p[x] = y;
hist.pb({sz[y], sz[y]});
sz[y] += sz[x];
hist.pb({cc, cc});
hist.pb({cc1, cc1});
cc--; cc1++;
}
void check_point(){
sizes.pb((int) hist.size());
}
void roll_back(){
while (hist.size() != sizes.back()){
hist.back().ff = hist.back().ss;
hist.pop_back();
}
sizes.pop_back();
}
};
vector<pii> ed[N], qs[N], d1[N], d2[N], f;
vector<int> out, mv;
int k;
dsu T[K], F;
void add(int v, int tl, int tr, int& l, int& r, pii x){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
ed[v].pb(x);
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
add(vv, tl, tm, l, r, x);
add(vv + 1, tm + 1, tr, l, r, x);
}
void solve(int v, int tl, int tr){
int s1 = (int) d1[v].size(), s2 = (int) d2[v].size();
for (int j = 0; j < k; j++) T[j].check_point();
for (auto [x, y]: ed[v]){
int V = max(x, y);
for (int j = 0; j < k; j++){
auto [l, r] = f[j];
if (V <= l){
T[j].unite(x, y);
}
}
d1[V].pb({x, y});
V = min(x, y) - 1;
for (int j = 0; j < k; j++){
auto [l, r] = f[j];
if (r <= V){
T[j].unite(x, y);
}
}
d2[V].pb({x, y});
}
if (tl == tr){
for (auto [v, ii]: qs[tl]){
for (int j = 0; j < k; j++){
auto [l, r] = f[j];
if (l <= v && v <= r){
F.check_point();
for (int s = l; s <= v; s++){
s = mv[s];
if (s > v) break;
for (auto [u1, u2]: d1[s]){
int v1 = T[j].get(u1);
int v2 = T[j].get(u2);
F.unite(v1, v2);
}
}
for (int s = v; s <= r; s++){
s = mv[s];
if (s > r) break;
for (auto [u1, u2]: d2[s]){
int v1 = T[j].get(u1);
int v2 = T[j].get(u2);
F.unite(v1, v2);
}
}
out[ii] = (T[j].cc - F.cc1);
F.roll_back();
break;
}
}
}
}
else {
int tm = (tl + tr) / 2, vv = 2 * v;
solve(vv, tl, tm);
solve(vv + 1, tm + 1, tr);
}
for (int j = 0; j < k; j++){
T[j].roll_back();
}
while (d1[v].size() != s1) d1[v].pop_back();
while (d2[v].size() != s2) d2[v].pop_back();
}
vector<int> simulateCollapse(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p){
int m = (int) t.size();
x.insert(x.begin(), 0);
y.insert(y.begin(), 0);
t.insert(t.begin(), 0);
for (int i = 1; i <= m; i++){
x[i]++; y[i]++;
}
int q = (int) w.size();
for (int i = 0; i < q; i++){
p[i]++; w[i]++;
}
const int S = min(m, 1200);
out.resize(q);
vector<int> c1(n + 1);
for (int i = 1; i <= m; i++){
c1[max(x[i], y[i])]++;
c1[min(x[i], y[i]) - 1]++;
}
int i = 1;
while (i <= n){
if (c1[i] >= S){
f.pb({i, i});
i++;
continue;
}
int j = i, sum = 0;
while (j <= n && sum < S){
if (c1[j] >= S){
j--;
break;
}
sum += c1[j];
j++;
}
f.pb({i, min(n, j)});
i = j + 1;
}
k = (int) f.size();
for (int i = 0; i < k; i++) T[i].init(n);
mv.resize(n + 2); mv[n + 1] = n + 1;
for (int i = n; i > 0; i--){
if (c1[i]) mv[i] = i;
else mv[i] = mv[i + 1];
}
map<pii, int> mp;
F.init(n);
for (int i = 1; i <= m; i++){
if (x[i] > y[i]) swap(x[i], y[i]);
if (!t[i]){
if (mp.find({x[i], y[i]}) == mp.end()){
mp[{x[i], y[i]}] = i;
}
}
else {
add(1, 1, m, mp[{x[i], y[i]}], i, {x[i], y[i]});
mp.erase({x[i], y[i]});
}
}
for (auto tt: mp){
add(1, 1, m, tt.ss, m, tt.ff);
}
for (int i = 0; i < q; i++) qs[w[i]].pb({p[i], i});
solve(1, 1, m);
return out;
}
