#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
const int BC=500;
vector<int> adj[100000], BB;
vector<tuple<int,int,int>> qry;
vector<pair<int,int>> E, L[100000], R[100000];
map<pair<int,int>,int> idx;
int N, ans[100000], B[100000], LL[100000], color[100000], cnt[100000], RR[100000];
bool EX[100000];
void flip_edge(int c, int i)
{
BB.push_back(c);
EX[c]^=1;
}
int find_(int a)
{
while(color[a]!=a) a=color[a];
return a;
}
void union_(int a, int b)
{
a=find_(a); b=find_(b);
if(a==b) return;
if(cnt[a]<cnt[b]) swap(a,b);
cnt[color[b]=a]+=cnt[b];
BB.push_back(b);
}
void restore(int sz)
{
while(BB.size()>sz) {
cnt[color[BB.back()]]-=cnt[BB.back()];
color[BB.back()]=BB.back();
BB.pop_back();
}
}
void solve(int s, int e)
{
int m=(s+e)>>1, bsz=BB.size(), bsz2;
for(auto[v,r]: L[s]) if(r>=e) union_(E[v].first,E[v].second);
for(auto[v,l]: R[e]) if(l<=s) union_(E[v].first,E[v].second);
if(s==e) {
ans[get<2>(qry[m])]=N-BB.size();
restore(bsz);
return;
}
bsz2=BB.size();
for(int i=m;++i<e;) for(auto[v,l]: R[i]) if(l<=s) union_(E[v].first,E[v].second);
solve(s,m);
restore(bsz2);
for(int i=m;i>s;i--) for(auto[v,r]: L[i]) if(r>=e) union_(E[v].first,E[v].second);
solve(m+1,e);
restore(bsz);
}
vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P)
{
int C=T.size(), Q=W.size(), w, p;
::N=N;
for(int i=0;i<C;i++) {
if(X[i]>Y[i]) swap(X[i],Y[i]);
if(idx.count({X[i],Y[i]})==0) {
idx[{X[i],Y[i]}]=E.size();
E.emplace_back(X[i],Y[i]);
}
B[i]=idx[{X[i],Y[i]}];
adj[X[i]].push_back(i);
adj[Y[i]].push_back(i);
}
for(int i=0;i<Q;i++) qry.emplace_back(W[i],P[i],i);
sort(qry.begin(),qry.end(),[&](tuple<int,int,int> a, tuple<int,int,int> b) {
if(get<0>(a)/BC!=get<0>(b)/BC) return get<0>(a)/BC<get<0>(b)/BC;
return get<1>(a)<get<1>(b);
});
memset(LL,w=p=-1,sizeof(LL));
memset(RR,-1,sizeof(RR));
for(int i=0;i<Q;i++) {
auto[cw,cp,j]=qry[i];
while(w<cw) {
int c=B[++w];
auto[a,b]=E[c];
if(a<=p && p<b) continue;
flip_edge(c,i);
}
while(w>cw) {
int c=B[w--];
auto[a,b]=E[c];
if(a<=p && p<b) continue;
flip_edge(c,i);
}
while(p<cp) {
int c=++p;
for(auto t: adj[c]) if(t<=w) flip_edge(B[t],i);
}
while(p>cp) {
int c=p--;
for(auto t: adj[c]) if(t<=w) flip_edge(B[t],i);
}
for(auto v: BB) if(RR[v]!=i) {
RR[v]=i;
if(LL[v]>-1 && !EX[v]) {
L[LL[v]].emplace_back(v,i-1);
R[i-1].emplace_back(v,LL[v]);
LL[v]=-1;
}
else if(LL[v]==-1 && EX[v]) LL[v]=i;
}
BB.clear();
}
for(int i=0;i<E.size();i++) if(EX[i]) {
L[LL[i]].emplace_back(i,Q-1);
R[Q-1].emplace_back(i,LL[i]);
}
for(int i=0;i<N;i++) cnt[color[i]=i]=1;
solve(0,Q-1);
return vector<int>(ans,ans+Q);
}
