#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
struct dsu{
vector<int> sz, p, rem;
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){
if (v != p[v]){
p[v] = get(p[v]);
}
return p[v];
}
void unite(int x, int y){
rem.pb(x); rem.pb(y);
x = get(x); y = get(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
p[x] = y;
sz[y] += sz[x];
cc--; cc1++;
}
void clear(){
for (int i: rem){
sz[i] = 1;
p[i] = i;
}
rem.clear();
cc1 = 0;
}
void complete(){
for (int i = 1; i <= n; i++){
sz[i] = 1;
p[i] = i;
}
cc = n;
}
};
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();
for (int i = 0; i < m; i++){
x[i]++; y[i]++;
if (x[i] > y[i]) swap(x[i], y[i]);
}
int q = (int) w.size();
vector<int> out(q);
for (int i = 0; i < q; i++){
p[i]++;
set<pii> st;
dsu T; T.init(n);
for (int j = 0; j <= w[i]; j++){
if (max(x[j], y[j]) > p[i]) continue;
if (t[j]) st.erase({x[j], y[j]});
else st.insert({x[j], y[j]});
}
for (auto [v1, v2]: st) T.unite(v1, v2);
out[i] += (T.cc - (n - p[i]));
T.complete(); st.clear();
for (int j = 0; j <= w[i]; j++){
if (min(x[j], y[j]) <= p[i]) continue;
if (t[j]) st.erase({x[j], y[j]});
else st.insert({x[j], y[j]});
}
for (auto [v1, v2]: st) T.unite(v1, v2);
out[i] += (T.cc - p[i]);
}
return out;
}
