#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]++;
}
}
};
ll n;
bool cmpa1( const pair<pair<ll,ll>,ll> &a, const pair<pair<ll,ll>,ll> &b){
if(a.fst.snd < b.fst.snd) return true;
else if(a.fst.snd > b.fst.snd) return false;
else if( a.fst.fst<b.fst.fst) return true;
else if( a.fst.fst>b.fst.fst) return false;
return a.snd<b.snd;
}
// en ari tienen que estar activos o que aparecen en ord
vector<int> solve(vector<pair<ll,ll>> ari, vector<pair<pair<ll,ll>,pair<ll,ll>>> ord, vector<pair<pair<ll,ll>,ll>> qu){
bool fij[SZ(ari)];
forn(i,0,SZ(ari)) fij[i]=true;
forn(i,0,SZ(ord)){
fij[ lower_bound(ALL(ari), ord[i].snd )-ari.begin() ]=false;
}
vector<pair<ll,ll>> lari; // ari sorted by left node
lari.pb({-1000,0});
forn(i,0,SZ(ari)) if(fij[i]) lari.pb(ari[i]);
vector<pair<ll,ll>> rari; // ari sorted by right node
forn(i,0,SZ(ari)) if(fij[i]) rari.pb({ari[i].snd,ari[i].fst});
sort(ALL(rari));
rari.pb({1000000000,0});
ll cnt = 0;
ll cmp1[SZ(rari)]; // desde 0 hasta i
UnionFind uf1(n);
vector<int> res(SZ(qu));
ll k = 0;
sort(ALL(qu));
forn(i,0,SZ(rari)){
while(k<SZ(qu) && qu[k].fst.snd<rari[i].fst){
UnionFind tmp(n);
ll rcnt = 0;
vector<ll> ract(SZ(ari),false);
forn(h,0,SZ(ord)) if(ord[h].snd.snd<=qu[k].fst.snd && ord[h].fst.fst<=qu[k].fst.fst){
/// cout<<ord[h].snd.fst<<" "<<ord[h].snd.snd<<'\n';
if(ract[lower_bound(ALL(ari), ord[h].snd )-ari.begin() ]) ract[lower_bound(ALL(ari), ord[h].snd )-ari.begin() ]=false;
else ract[lower_bound(ALL(ari), ord[h].snd )-ari.begin() ]=true;
}
forn(h,0,SZ(ract)) if(ract[h]){ //cout<<ari[h].fst<<" "<<ari[h].snd<<" se puede usar\n";
if(tmp.Find(uf1.Find(ari[h].fst))!=tmp.Find(uf1.Find(ari[h].snd))){
tmp.Union(uf1.Find(ari[h].fst), uf1.Find(ari[h].snd));
rcnt++;
}
}
ll rres = (i-1>=0?cmp1[i-1]:0) - rcnt + qu[k].fst.snd+1 - (i-1>=0?rari[i-1].fst+1:0);
/// cout<<qu[k].fst.fst<<" "<<qu[k].fst.snd<<" left "<<(i-1>=0?cmp1[i-1]:0)<<" - "<< rcnt<<" + "<< qu[k].fst.snd+1 <<" - "<< (i-1>=0?rari[i-1].fst+1:0)<<'\n';
res[k]=rres;
k++;
}
if(rari[i].fst==1000000000) break;
if(uf1.Find(rari[i].fst)!=uf1.Find(rari[i].snd)){
cnt++;
uf1.Union(rari[i].fst,rari[i].snd);
}
cmp1[i]= rari[i].fst+1 - cnt;
}
// cout<<"--------------------\n";
sort(ALL(qu),cmpa1);
k=0;
cnt = 0;
ll cmp2[SZ(lari)]; // desde n hasta i
UnionFind uf2(n);
for(int i = SZ(lari)-1; i>=0; i--){
while(k<SZ(qu) && qu[k].fst.snd+1>lari[i].fst){
UnionFind tmp(n);
ll rcnt = 0;
vector<ll> ract(SZ(ari),0);
forn(h,0,SZ(ord)) if(ord[h].snd.fst>=qu[k].fst.snd+1 && ord[h].fst.fst<=qu[k].fst.fst){
//cout<<ord[h].snd.fst<<" "<<ord[h].snd.snd<<'\n';
if(ract[ lower_bound(ALL(ari), ord[h].snd) - ari.begin() ]) ract[ lower_bound(ALL(ari) , ord[h].snd) - ari.begin()]=false;
else ract[ lower_bound(ALL(ari), ord[h].snd)- ari.begin()] = true;
}
forn(h,0,SZ(ari)) if(ract[h]){ //cout<<" se puede usar "<<ari[h].fst<<" "<<ari[h].snd<<'\n';
if(tmp.Find(uf2.Find(ari[h].fst))!=tmp.Find(uf2.Find(ari[h].snd))){
tmp.Union(uf2.Find(ari[h].fst),uf2.Find(ari[h].snd));
rcnt++;
}
}
ll rres = (i+1<SZ(lari)?cmp2[i+1]:0) -rcnt + (n-(qu[k].fst.snd+1)) - (i+1<SZ(lari)?n-(lari[i+1].fst+1):0);
//cout<<qu[k].fst.fst<<" "<<qu[k].fst.snd<<" right "<<(i+1<SZ(lari)?cmp2[i+1]:0)<<" - "<<rcnt<<" + "<<(n-(qu[k].fst.snd+1))<<" - "<< (i+1<SZ(lari)?n-(lari[i+1].fst+1):0)<<'\n';
res[qu[k].snd]+=rres;
k++;
}
if(lari[i].fst<0) break;
if(uf2.Find(lari[i].fst)!=uf2.Find(lari[i].snd)){
cnt++;
uf2.Union(lari[i].fst,lari[i].snd);
}
cmp2[i]=(n-lari[i].fst) - cnt;
}
return res;
}
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) {
n=N;
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>,pair<ll,ll>>> ord;
forn(i,0,SZ(T)) ord.pb({{i,T[i]},{min(X[i],Y[i]),max(X[i],Y[i])}});
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 = solve(ari,ord,qu);
return res;
}
