Yannik @ 2024-09-26 19:47:51
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e5+10;
int T,n,m,k;
int x[N],y[N],z[N];
int ans[N];
map<int,int> mp;
vector<int> g[N];
struct dsu{
vector<int> f;
dsu(int n):f(n){
iota(f.begin(),f.end(),0);
}
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
bool merge(int a,int b){
int fa=find(a),fb=find(b);
if(fa==fb) return false;
f[fb]=fa;
return true;
}
bool same(int a,int b){
return find(a)==find(b);
}
};
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
dsu ds(n+1);
for(int i=1;i<=m;i++){
cin>>x[i]>>y[i];
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
cin>>k;
for(int i=1;i<=k;i++){
cin>>z[i];
mp[z[i]]=1;
}
ans[k+1]=n;
for(int i=1;i<=m;i++){
if(!mp[x[i]]&&!mp[y[i]]){
ds.merge(x[i],y[i]);
ans[k+1]--;
}
}
for(int i=k;i>=1;i--){
ans[i]=ans[i+1];
mp[z[i]]=0;
for(auto t:g[z[i]]){
if(!ds.same(t,z[i])&&!mp[t]){
ans[i]--;
ds.merge(t,z[i]);
}
}
}
for(int i=1;i<=k+1;i++){
cout<<ans[i]-i+1<<"\n";
}
return 0;
}