链接: https://cses.fi/problemset/task/3303

板块: Advanced Graph Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

有 $n$ 座城市和 $m$ 条道路。每条道路都是双向的，连接两座城市。已知其中有 $k$ 座城市设有动漫商店。

如果你住在某座城市，当然会熟悉当地的动漫商店（如果有的话）。你想找到离你所在城市最近、但不位于你这座城市的动漫商店。

对于每座城市，求出到另一座设有动漫商店的城市的最短距离。

输入

第一行包含三个整数 $n$、$m$ 和 $k$：城市数量、道路数量和动漫商店数量。城市编号为 $1,2,\dots,n$。

下一行包含 $k$ 个整数：设有动漫商店的城市。

最后有 $m$ 行描述道路。每行包含两个整数 $a$ 和 $b$：表示城市 $a$ 与 $b$ 之间有一条道路。

输出

输出 $n$ 个整数：对于每座城市，到另一座设有动漫商店的城市的最短距离。如果没有这样的城市，则输出 $-1$。

数据范围

$1 \le k \le n \le 10^5$ $0 \le m \le 2 \cdot 10^5$

样例输入

9 6 4
2 4 5 7
1 2
1 3
1 8
2 4
3 4
5 6

样例输出

1 1 1 1 -1 1 -1 2 -1