#include "collapse.h"
#include <bits/stdc++.h>
#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i<b; i++)
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
struct UnionFind{
ll n;
vector<ll> p;
vector<ll> sz;
UnionFind(ll n=0):n(n),p(n,0),sz(n,1){
forn(i,0,n) p[i]=i;
}
ll Find(ll x){
return (p[x]==x?x:Find(p[x]));
}
void Union(ll a,ll b){
ll pa = Find(a);
ll pb = Find(b);
if(pa==pb) return;
if(sz[pa]<sz[pb]){
p[pa]=pb;
}else{
p[pb]=pa;
if(sz[pa]==sz[pb]) sz[pa]++;
}
}
};
std::vector<int> simulateCollapse(
int N,
std::vector<int> T,
std::vector<int> X,
std::vector<int> Y,
std::vector<int> W,
std::vector<int> P) {
vector<pair<ll,ll>> ari;
forn(i,0,SZ(X)) ari.pb({min(X[i],Y[i]),max(X[i],Y[i])});
sort(ALL(ari));
ari.erase(unique(ALL(ari)),ari.end());
vector<bool> act(SZ(ari),false);
vector<pair<pair<ll,ll>,ll>> qu; forn(i,0,SZ(W)) qu.pb({{W[i],P[i]},i});
sort(ALL(qu));
vector<int> res(SZ(qu));
ll j = 0;
forn(i,0,SZ(qu)){
//cout<<"para la querie "<<qu[i].fst.fst<<" "<<qu[i].fst.snd<<'\n';
UnionFind uf(N);
while(j<=qu[i].fst.fst){
ll ind = lower_bound(ALL(ari),(pair<ll,ll>){min(X[j],Y[j]),max(X[j],Y[j])})-ari.begin();
//cout<<ind<<'\n';
if(act[ind]) act[ind]=false;
else act[ind]=true;
j++;
}
ll cnt = N;
forn(h,0,SZ(act)){
if(act[h] && (ari[h].snd<=qu[i].fst.snd || ari[h].fst>=qu[i].fst.snd+1)){
//cout<<ari[h].fst<<" "<<ari[h].snd<<'\n';
if(uf.Find(ari[h].fst)!=uf.Find(ari[h].snd)){
cnt--;
uf.Union(ari[h].fst,ari[h].snd);
}
}
}
res[qu[i].snd]=cnt;
}
return res;
}
