#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 bit(s,i) (((s)>>(i))&1)
#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
#define __builtin_popcount __builtin_popcountll
#define _ << " " <<
template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}
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];
vector<pair<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 : 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.eb(par[y],par[y]);
history.eb(sz[x],sz[x]);
par[y]=x;
sz[x]+=sz[y];
return true;
}
int snapshot(){
return sz(history);
}
void rollback(int x){
while(sz(history)>x){
history.back().fi=history.back().se;
history.pop_back();
}
}
} dsu;
vi simulateCollapse(int nn, vi tt, vi xx, vi yy, vi ww, vi pp){
n=nn,c=sz(tt),q=sz(ww);
del.resize(c,c);
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{
del[mp[{xx[i],yy[i]}]]=i;
}
}
vi id(q),ans(q,0);
iota(all(id),0);
sort(all(id),[&](int x, int y){return ww[x]<ww[y];});
int l=0, lq=0;
while(l<c){
int r=min(c-1,l+B);
/// reset
rep(i,n){
que[i].clear();
ed[i].clear();
red[i].clear();
}
exEd.clear();
/// prepare for queries
while(lq<q && ww[id[lq]]<=r){
que[pp[id[lq]]].eb(id[lq]);
++lq;
}
/// prepare for adding edges
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);
}
}
}
/// sweep line for answer queries offline
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(), cnt=0;
rep(k,sz(exEd)){
int ide=exEd[k];
if(yy[ide]<=i && del[ide]>ww[j]){
dsu.unite(xx[ide], yy[ide]);
--cc; ++cnt;
}
}
foru(k,l,ww[j]){
if(tt[k]==0 && yy[k]<=i && del[k]>ww[j]){
dsu.unite(xx[k], yy[k]);
--cc; ++cnt;
}
}
ans[j]+=cc;
cc+=cnt;
dsu.rollback(tmp);
}
}
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(), cnt=0;
rep(k,sz(exEd)){
int ide=exEd[k];
if(xx[ide]>=i && del[ide]>ww[j]){
dsu.unite(xx[ide],yy[ide]);
--cc; ++cnt;
}
}
foru(k,l,ww[j]){
if(tt[k]==0 && xx[k]>=i && del[k]>ww[j]){
dsu.unite(xx[k], yy[k]);
--cc; ++cnt;
}
}
ans[j]+=cc;
cc+=cnt;
dsu.rollback(tmp);
}
}
l=r+1;
}
return ans;
}
