某地区有 N 个小区(编号为 1 到 N),有 M 条双向的道路连接这些小区,每条道路连接了两个不同的小区,N 个小区通过 M 条双向道路连接成为了一个大型社区,社区中任意两个小区都可以通过 1 条或多条道路相连。
其中有 K 个小区中建有社区超市,第 i 个超市建在编号为 C_i 的小区,每个小区中最多建有 1 个社区超市。
请编程求解出,对于社区中的每个小区中的居民,到最近的社区超市,最少要经过多少条道路?
第 1 行包含三个整数 N,M,K,分别表示小区数量、道路数量以及社区超市数量。
第 2 行包含 K 个整数,表示建有社区超市的小区编号。
接下来 M 行,每行包含两个整数 u,v,表示小区 u 与小区 v 之间有一条双向道路,两个小区之间可能有多条道路相连。
输出一行 N 个整数,第 i 个整数表示小区 i 到最近社区超市所需经过的最少道路数量。
如果小区 i 本身有社区超市,则该位置输出 0。
5 8 1 3 1 2 2 3 3 4 4 5 1 5 1 3 2 4 2 5
1 1 0 1 2
10 15 5 1 5 7 9 10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 1 6 2 7 3 8 4 9 1 10 2 5
0 1 2 1 0 1 0 1 0 0
12 25 3 4 8 10 1 2 1 9 2 3 2 8 2 9 3 4 3 6 3 10 4 5 4 12 5 6 5 8 6 7 6 8 6 9 6 10 7 8 7 9 7 12 8 9 8 12 9 10 9 11 10 11 11 12
2 1 1 0 1 1 1 0 1 0 1 1
对于 30\% 的数据,满足 N \le 1000,M \le 2000,K=1。
对于 60\% 的数据,满足 N \le 10000,M \le 20000。
对于 100\% 的数据,满足 1 \le N \le 10^5,1 \le N-1 \le M \le 10^5,1 \le K \le N,1 \le C_i \le N, \le u \neq v \le N。