#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;
stack<tuple<int,int,bool>>st;
void merge(int x,int y){
x=dsu(x);
y=dsu(y);
if(x==y)return;
if(p[x]<p[y])swap(x,y);
st.push({x,p[x],(p[x]==p[y])});
if(p[x]==p[y]){
p[y]--;
}
sz--;
p[x]=y;
}
void rollback(int t){
while(st.size()>t){
auto [x,pxe,ch]=st.top();
st.pop();
if(ch){
p[p[x]]++;
}
p[x]=pxe;
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 sl2(int l,int r,vector<int>&x,vector<int>&y,vector<int>&ord,vector<int>&w,int lim){
if(l>r)return;
if(l==r){
while(ord.size()&&w[ord.back()]==l-1){
ans[ord.back()]=sz;
ord.pop_back();
}
return;
}
int mid=(l+r)>>1ll;
int cur=st.size();
for(int i=mid+1;i<=r;i++){
if(x[i]<=lim&&lim+1<=y[i])continue;
if(pos[i]<l){
merge(x[i],y[i]);
}
}
sl2(l,mid,x,y,ord,w,lim);
rollback(cur);
for(int i=l;i<=mid;i++){
if(x[i]<=lim&&lim+1<=y[i])continue;
if(pos[i]>r){
merge(x[i],y[i]);
}
}
sl2(mid+1,r,x,y,ord,w,lim);
rollback(cur);
}
void solve2(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;
pos[m]=i.second;
x.push_back(i.first.first);
y.push_back(i.first.second);
m++;
}
x.push_back(0);
y.push_back(0);
m++;
for(int i=0;i<n;i++){
p[i]=-1;
}
vector<int>ord;
for(int i=0;i<q;i++){
ord.push_back(i);
}
sz=n;
sort(ord.begin(),ord.end(),[&w](int x,int y){
return w[x]>w[y];
});
sl2(0,m-1,x,y,ord,w,ps.front());
}
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,-1);
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(t,x,y,w,ps);
return ans;
}
return ans;
}
