#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]++;
}
int q = (int) w.size();
vector<pii> qs[m];
for (int i = 0; i < q; i++){
p[i]++;
qs[w[i]].pb({p[i], i});
}
const int S = sqrt(m);
vector<int> out(q);
vector<int> c1(n + 1);
for (int i = 0; i < m; i++){
c1[max(x[i], y[i])]++;
c1[min(x[i], y[i]) - 1]++;
}
vector<pii> f;
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;
}
int k = (int) f.size();
dsu T[k];
for (int i = 0; i < k; i++) T[i].init(n);
vector<int> move(n + 2); move[n + 1] = n + 1;
for (int i = n; i > 0; i--){
if (c1[i]) move[i] = i;
else move[i] = move[i + 1];
}
vector<pii> d[n + 1];
dsu F; F.init(n);
for (int i = 0; i < m; i++){
int v = max(x[i], y[i]);
for (int j = 0; j < k; j++){
auto [l, r] = f[j];
if (v <= l){
T[j].unite(x[i], y[i]);
}
}
d[v].pb({x[i], y[i]});
for (auto [v, ii]: qs[i]){
for (int j = 0; j < k; j++){
auto [l, r] = f[j];
if (l <= v && v <= r){
for (int s = l; s <= v; s++){
s = move[s];
if (s > v) break;
for (auto [u1, u2]: d[s]){
int v1 = T[j].get(u1);
int v2 = T[j].get(u2);
F.unite(v1, v2);
}
}
out[ii] += (T[j].cc - (n - v) - F.cc1);
F.clear();
break;
}
}
}
}
for (int i = 0; i < k; i++) T[i].complete();
for (int i = 1; i <= n; i++) d[i].clear();
for (int i = 0; i < m; i++){
int v = min(x[i], y[i]) - 1;
for (int j = 0; j < k; j++){
auto [l, r] = f[j];
if (r <= v){
T[j].unite(x[i], y[i]);
}
}
d[v].pb({x[i], y[i]});
for (auto [v, ii]: qs[i]){
for (int j = 0; j < k; j++){
auto [l, r] = f[j];
if (l <= v && v <= r){
for (int s = v; s <= r; s++){
s = move[s];
if (s > r) break;
for (auto [u1, u2]: d[s]){
int v1 = T[j].get(u1);
int v2 = T[j].get(u2);
F.unite(v1, v2);
}
}
out[ii] += (T[j].cc - v - F.cc1);
F.clear();
break;
}
}
}
}
return out;
}
