题目描述
众所周知,Birmingham的赛马非常有名,这些赛马比赛都会在固定的时间进行。但是,还有些鲜为人知的是,在这些赛马比赛背后,有一些能够操纵比赛的人(即知道获胜者),他们会在秘密会议上开会,并在第二天开始向全市传播。
在会议结束后的第一天,所有知道内幕信息的人都会向理他们住所最多步远的人分享内幕信息。
在会议结束后的第二天,所有知道内幕信息的人也都会向理他们家最远步远的人分享内幕信息。
也就是说,在会议结束后的第天,所有知道内幕信息的人都会向离他们家最远步远的人分享这些信息。
现在,我们可以知道Birmingham市的地图信息,其中顶点表示房屋,边表示连接这些房屋的路径。房屋是通过编号1到N来表示的,我们可以认为一个人可以一步走完一条边,且通过一系列的道路,他们都可以从自己的房子到达每个房子。
现在,你的任务是,计算出居住在每一个房子的人,他们能在第几天知晓内幕信息。
输入格式
第一行输入四个整数(),表示Birmingham房屋的数量,道路的数量,参加秘密会议的人的数量和的值。
接下来一行,包含个数字,表示第个参加秘密会议的人在Birmingham市的住所编号.
接下来行,每行两个数字和(),表示在房屋和房屋之间有一条路。
输出格式
输出个用空格隔开的数字,表示住在编号为的房屋里的人会在秘密会议后第几天知道内幕消息。参加秘密会议的人知晓内幕消息的时间认为是0.
样例
输入样例1
复制6 8 1 1
6
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
输出样例1
复制1 1 2 2 1 0
输入样例2
复制6 8 2 1
6 4
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
输出样例2
复制1 1 1 0 1 0
输入样例3
复制6 8 1 2
6
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
输出样例3
复制1 1 1 2 1 0
_____________________________________________________________________________
写作不易,点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
_____________________________________________________________________________
#include <bits/stdc++.h>
using namespace std;
long long n,m,q,k;
vector<long long>a[100005];
long long b[100005];
long long c[100005];
void bfs(){
queue<int> Q;
int bz=n;
for(int i=1;i<=q;i++){
Q.push(b[i]);
c[b[i]]=0;
bz--;
}
int i=1;
while(bz!=0){
for(int j=1;j<=i*k;j++){
int l=Q.size();
for(int k=1;k<=l;k++){
int d=Q.front();
Q.pop();
for(auto v:a[d]){
if(c[v]==-1)bz--,c[v]=i,Q.push(v);
if(bz==0)return;
}
}
}
i++;
}
}
int main(){
cin>>n>>m>>q>>k;
for(long long i=1;i<=n;i++)c[i]=-1;
for(long long i=1;i<=q;i++)cin>>b[i];
for(long long i=1;i<=m;i++){
long long x,y;
cin>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
bfs();
for(long long j=1;j<=n;j++)cout<<c[j]<<" ";
}