#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+100;
#define ll long long
int n,m,q;
int p[N];
int r[N];
int dsu(int x){
if(p[x]<0)return x;
return p[x]=dsu(p[x]);
}
bool merge(int x,int y){
x=dsu(x);
y=dsu(y);
if(x==y)return 0;
if(p[x]<p[y])swap(x,y);
p[y]+=p[x];
p[x]=y;
return 1;
}
vector<int> simulateCollapse(int _n,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P) {
n=_n;
m=X.size();
q=W.size();
vector<int>ans(q,0);
{
map<pair<int,int>,int>s;
for(int i=m-1;i>=0;i--){
if(X[i]>Y[i])swap(X[i],Y[i]);
r[i]=m+1;
if(T[i]==1){
s[{X[i],Y[i]}]=i;
}
else{
r[i]=s[{X[i],Y[i]}];
if(r[i]==0){
r[i]=m+1;
}
}
}
}
for(int i=0;i<q;i++){
ans[i]=n;
for(int j=0;j<n;j++){
p[j]=-1;
}
for(int j=0;j<=W[i];j++){
if(X[j]<=P[i]&&P[i]+1<=Y[j])continue;
if(T[j]==0&&r[j]>W[i]){
if(merge(X[j],Y[j])){
ans[i]--;
}
}
}
}
return ans;
}
