#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#include "collapse.h"
int cur[100001];
int vis[100001];
int par[100001];
int ss[100001];
int find(int no){
if(par[no]==no){
return no;
}
return find(par[no]);
}
vector<pair<int,int>> kk[3];
vector<pair<int,int>> pre[100001];
vector<pair<int,int>> pre2[100001];
vector<pair<int,int>> pre3[100001];
vector<int> pre4[100001];
int co=0;
void merge(int aa,int bb,int i){
/*if(i==0){
cout<<aa<<":"<<bb<<endl;
}*/
int x=find(aa);
int y=find(bb);
if(x==y){
kk[i].pb({-1,-1});
}
else{
if(ss[x]<ss[y]){
swap(x,y);
}
co--;
par[y]=x;
ss[x]+=ss[y];
kk[i].pb({x,y});
}
}
void rollback(int i){
assert(kk[i].size()>0);
if(kk[i].back().a==-1){
kk[i].pop_back();
}
else{
pair<int,int> no=kk[i].back();
co++;
par[no.b]=no.b;
ss[no.a]-=ss[no.b];
kk[i].pop_back();
}
}
vector<int> simulateCollapse(
int n,
vector<int> tt,
vector<int> aa,
vector<int> bb,
vector<int> ww,
vector<int> pp
) {
int m=aa.size();
int q=ww.size();
vector<int> cc;
map<pair<int,int>,int> ss2;
int ind=0;
const int ee=300;
for(int j=0;j<m;j++){
cur[j]=0;
}
for(int i=0;i<q;i++){
pre3[(ww[i]-(ww[i]%ee))].pb({ww[i],i});
}
for(int i=0;i<m;i++){
if(aa[i]>bb[i]){
swap(aa[i],bb[i]);
}
if(ss2.find({aa[i],bb[i]})!=ss2.end()){
cc.pb(ss2[{aa[i],bb[i]}]);
}
else{
ss2[{aa[i],bb[i]}]=ind;
cc.pb(ind);
cur[ind]=0;
ind++;
pre2[aa[i]].pb({ss2[{aa[i],bb[i]}],bb[i]});
pre[bb[i]].pb({ss2[{aa[i],bb[i]}],aa[i]});
}
}
vector<int> ans;
for(int i=0;i<q;i++){
ans.pb(0);
}
int kk2=-1;
for(int i=0;i<m;i+=ee){
for(int j=kk2+1;j<i;j++){
cur[cc[j]]^=1;
}
kk2=i-1;
for(int j=0;j<n;j++){
pre4[j].clear();
}
for(auto j:pre3[i]){
pre4[pp[j.b]].pb(j.b);
}
for(int j=0;j<m;j++){
vis[j]=0;
}
co=n;
for(int j=0;j<3;j++){
kk[j].clear();
}
for(int j=0;j<n;j++){
par[j]=j;
ss[j]=1;
}
vector<int> ll;
for(int j=i;j<i+ee and j<m;j++){
if(vis[cc[j]]==0){
ll.pb(j);
}
vis[cc[j]]=1;
}
for(int j=0;j<3;j++){
kk[j].clear();
}
for(int ii=n-1;ii>=0;ii--){
for(auto j:pre2[ii]){
if(vis[j.a]==0 and cur[j.a]==1){
merge(ii,j.b,0);
//cout<<ii<<"::"<<j.b<<endl;
}
}
}
for(int ii=0;ii<n;ii++){
for(auto j:pre2[ii]){
if(vis[j.a]==0 and cur[j.a]==1){
// cout<<11<<endl;
rollback(0);
}
}
for(auto j:pre[ii]){
if(vis[j.a]==0 and cur[j.a]==1){
merge(ii,j.b,1);
}
}
for(auto j:pre4[ii]){
int w=ww[j];
for(int x=i;x<=w;x++){
cur[cc[x]]^=1;
}
for(auto x:ll){
// cout<<x<<",,"<<cur[x]<<":"<<par[x]<<endl;
if(cur[cc[x]]==1 and (bb[x]<=ii or aa[x]>ii)){
// cout<<aa[x]<<":"<<bb[x]<<":"<<x<<endl;
merge(aa[x],bb[x],2);
}
}
for(int x=i;x<=w;x++){
cur[cc[x]]^=1;
}
ans[j]=co;
while(kk[2].size()){
rollback(2);
}
}
}
}
return ans;
}
