#include "collapse.h"
#include<bits/stdc++.h>
using namespace std;
#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define fi first
#define se second
#define ll long long
#define eb emplace_back
#define pb push_back
const int B=300;
const int N=1e5+5;
int n,c,q;
vi del;
map<ii,int> mp;
vector<int> ed[N],red[N],que[N],exEd;
struct DSU{
int par[N], sz[N];
// safe history: (type, index, old_value)
// type 0 -> par[idx] old value
// type 1 -> sz[idx] old value
vector<tuple<int,int,int>> history;
DSU(){
memset(par,0,sizeof(par));
memset(sz,0,sizeof(sz));
history.clear();
}
void init(int n){
history.clear();
iota(par, par+n, 0);
fill(sz, sz+n, 1);
}
int find(int x){
return par[x]==x ? x : par[x]=find(par[x]);
}
bool unite(int x, int y){
x=find(x); y=find(y);
if(x==y) return false;
if(sz[x]<sz[y]) swap(x,y);
history.emplace_back(0, y, par[y]);
history.emplace_back(1, x, sz[x]);
par[y]=x;
sz[x]+=sz[y];
return true;
}
int snapshot(){ return (int)history.size(); }
void rollback(int x){
while((int)history.size()>x){
auto [type, idx, old] = history.back(); history.pop_back();
if(type==0) par[idx]=old; else sz[idx]=old;
}
}
} dsu;
vi simulateCollapse(int nn, vi tt, vi xx, vi yy, vi ww, vi pp){
n=nn; c=sz(tt); q=sz(ww);
del.assign(c, c);
mp.clear();
// Normalize vertex indices to 0-based if they appear 1-based
bool one_based_vertices=false;
rep(i,c) if(xx[i]==n || yy[i]==n) { one_based_vertices=true; break; }
if(one_based_vertices) rep(i,c){ xx[i]--; yy[i]--; }
// Normalize pp (positions) to 0-based if needed
bool one_based_pos=false;
rep(i,q) if(pp[i]==n) { one_based_pos=true; break; }
if(one_based_pos) rep(i,q) pp[i]--;
rep(i,c){
if(xx[i]>yy[i]) swap(xx[i], yy[i]);
if(tt[i]==0){ // add
mp[{xx[i], yy[i]}]=i;
} else { // delete
auto it = mp.find({xx[i], yy[i]});
if(it!=mp.end()) del[it->second]=i;
else {
// unmatched delete - ignore defensively
}
}
}
vi id(q), ans(q,0);
iota(all(id), 0);
sort(all(id), [&](int a, int b){ return ww[a] < ww[b]; });
int l=0, lq=0;
while(l<c){
int r=min(c-1, l+B);
// clear buckets
rep(i,n){ que[i].clear(); ed[i].clear(); red[i].clear(); }
exEd.clear();
// prepare queries whose position p <= r
while(lq<q && ww[id[lq]]<=r){
if(pp[id[lq]]>=0 && pp[id[lq]]<n) que[pp[id[lq]]].eb(id[lq]);
++lq;
}
// prepare edges added before block
rep(i,l) if(tt[i]==0){
if(del[i]>=l){
if(del[i]>r){
ed[yy[i]].eb(i);
red[xx[i]].eb(i);
} else {
exEd.eb(i);
}
}
}
// forward sweep
int cc=0;
dsu.init(n);
rep(i,n){
++cc;
for(int j: ed[i]) if(dsu.unite(xx[j], yy[j])) --cc;
for(int j: que[i]){
int tmp = dsu.snapshot();
int cnt = 0;
rep(k, (int)exEd.size()){
int ide = exEd[k];
if(yy[ide] <= i && del[ide] > ww[j]){
if(dsu.unite(xx[ide], yy[ide])) { --cc; ++cnt; }
}
}
foru(k, l, ww[j]){
if(tt[k]==0 && yy[k] <= i && del[k] > ww[j]){
if(dsu.unite(xx[k], yy[k])) { --cc; ++cnt; }
}
}
ans[j] += cc;
cc += cnt;
dsu.rollback(tmp);
}
}
// backward sweep
cc = 0;
dsu.init(n);
ford(i, n-1, 1){
++cc;
for(int j: red[i]) if(dsu.unite(xx[j], yy[j])) --cc;
for(int j: que[i-1]){
int tmp = dsu.snapshot();
int cnt = 0;
rep(k, (int)exEd.size()){
int ide = exEd[k];
if(xx[ide] >= i && del[ide] > ww[j]){
if(dsu.unite(xx[ide], yy[ide])) { --cc; ++cnt; }
}
}
foru(k, l, ww[j]){
if(tt[k]==0 && xx[k] >= i && del[k] > ww[j]){
if(dsu.unite(xx[k], yy[k])) { --cc; ++cnt; }
}
}
ans[j] += cc;
cc += cnt;
dsu.rollback(tmp);
}
}
l = r + 1;
}
return ans;
}
