#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 pos[N];
vector<int>ans;
int dsu(int x){
while(p[x]>=0)x=p[x];
return x;
}
int sz;
void merge(int x,int y){
x=dsu(x);
y=dsu(y);
if(x==y)return;
if(p[x]<p[y])swap(x,y);
if(p[x]==p[y])p[y]--;
p[x]=y;
sz--;
}
void solve1(vector<int>&t,vector<int>&x,vector<int>&y,vector<int>&w,vector<int>&ps){
map<pair<int,int>,int>last;
for(int i=0;i<m;i++){
if(x[i]>y[i])swap(x[i],y[i]);
if(last.count({x[i],y[i]})){
pos[i]=last[{x[i],y[i]}];
pos[pos[i]]=i;
last.erase({x[i],y[i]});
}
else{
last[{x[i],y[i]}]=i;
}
}
for(auto i:last){
pos[i.second]=m;
}
for(int i=0;i<q;i++){
for(int j=0;j<n;j++){
p[j]=-1;
}
sz=n;
for(int j=0;j<=w[i];j++){
if(x[j]<=ps[i]&&ps[i]+1<=y[j]){
continue;
}
if(pos[j]>w[i]){
merge(x[j],y[j]);
}
}
ans[i]=sz;
}
}
void solve2(){
}
vector<int> simulateCollapse(int _n,vector<int> t,vector<int> x,vector<int> y,vector<int> w,vector<int> ps) {
n=_n;
m=x.size();
q=w.size();
ans.resize(q,0);
if(n<=5000&&m<=5000&&q<=5000){
solve1(t,x,y,w,ps);
return ans;
}
if(is_sorted(ps.begin(),ps.end())&&ps.front()==ps.back()){
solve2();
return ans;
}
return ans;
}
