#include<bits/stdc++.h>
#include "collapse.h"
using namespace std;
#define sz(a) (int)a.size()
#define all(x) x.begin(),x.end()
#define ii pair<int,int>
#define se second
#define fi first
#define pb push_back
#define emb emplace_back
const int N=1e6+5,lg=30,mod=1e9+7;
vector<ii>req[N];
bool k[N];
struct DSU
{
int n;
vector<int>r;
DSU(){};
DSU(int _n):n(_n),r(n+5,-1){};
int acs(int u){
return r[u]<0?u:r[u]=acs(r[u]);
}
bool join(int u,int v){
u=acs(u);
v=acs(v);
if(u!=v){
if(r[u]>r[v])swap(u,v);
r[u]+=r[v];
r[v]=u;
return true;
}
return false;
}
};
struct segsum {
int n;
vector<int> st;
segsum() {};
segsum(int _n): n(_n), st(n * 4 + 5, 0){};
void update(int id, int l, int r, int i, int val) {
if (l ==r) {
st[id] += val ;
return;
}
int mid = (l + r) >> 1;
if(i<=mid)
update(id << 1, l, mid, i, val);
else
update(id << 1 | 1, mid + 1, r, i, val);
st[id] = st[id << 1] + st[id << 1 | 1];
}
int get(int id, int l, int r, int u, int v) {
if (r < u || l > v) return 0;
if (l >= u && r <= v) return st[id];
int mid = (l + r) >> 1;
return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
}
};
vector<int> simulateCollapse(int node,vector<int>t,vector<int>x,vector<int>y,vector<int>w,vector<int>p){
int query=sz(w),edge=sz(t);
--node;
DSU dsu(node);
vector<int>ans(query);
for(int i=0;i<edge;++i){
if(y[i]<x[i])swap(x[i],y[i]);
k[i]=dsu.join(x[i],y[i]);
}
for(int i=0;i<query;++i){
req[w[i]].emb(p[i],i);
}
segsum dau(node),cuoi(node);
int sum=node;
for(int i=0;i<edge;++i){
dau.update(1,0,node,x[i],k[i]);
cuoi.update(1,0,node,y[i],k[i]);
for(auto x:req[i]){
int val=dau.get(1,0,node,x.fi+1,node);
int val1=cuoi.get(1,0,node,1,x.fi);
ans[x.se]=node-val-val1;
}
}
return ans;
}
// main()
// {
// srand(time(0));
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
// #define task "aws"
// if(fopen(task".inp","r")){
// freopen(task".inp","r",stdin);
// freopen(task".out","w",stdout);
// }
// int node;
// vector<int>t,x,y,w,q;
// cin >> node;
// int a,b,c;
// while(cin >>a >> b >> c){
// if(!a&&!b&&!c)break;
// t.emb(a);
// x.emb(b);
// y.emb(c);
// }
// while(cin >> a >> b){
// w.emb(a);
// q.emb(b);
// }
// simulateCollapse(node,t,x,y,w,q);
// }
/*
3
0 1 2
0 1 3
0 2 3
1 2
2 3
*/
