考虑对每个点的度数进行分治。

若一个点的度数小于 $\sqrt{N}$，直接暴力修改它的相邻点。

若一个点的度数大于 $\sqrt{N}$，则打 tag 记录它修改的颜色和时间戳。由于这样的点是有限的所以一个点最多有 $2\sqrt{N}$ 个相邻的这样的点。到时候修改或者最终求答案的时候直接遍历这些 tag 就行了。

时间复杂度 $O(N\sqrt{N})$。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=1010;
int tag1[M],tag2[M],len;
vector<int>G[N],e[N];
int c[N],t[N],rd[N],B,b[N];
void pushup(int p)
{
	for(int y:e[p])
		if(tag2[y]>t[p])
			c[p]=tag1[y],t[p]=tag2[y];
}
signed main()
{
	int n,m,q;cin>>n>>m>>q;B=sqrt(n);
	for(int i=1;i<=m;i++)
	{
		int x,y;cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
		rd[x]++,rd[y]++;
	}
	for(int i=1;i<=n;i++)if(rd[i]>B)
	{
		b[i]=++len;
		for(int y:G[i])e[y].push_back(len);
	}
	for(int i=1;i<=n;i++)c[i]=i,t[i]=0;
	for(int i=1;i<=q;i++)
	{
		int x;cin>>x;
		pushup(x);
		if(b[x])tag1[b[x]]=c[x],tag2[b[x]]=i;
		else for(int y:G[x])c[y]=c[x],t[y]=i;
	}
	for(int i=1;i<=n;i++)pushup(i);
	for(int i=1;i<=n;i++)cout<<c[i]<<' ';cout<<'\n';
	return 0;
}