题目描述

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

如果你住在某座城市，并且这座城市本身有动漫商店，那么你当然已经很熟悉本地的动漫商店了。现在你想找到一座不在自己所在城市的最近动漫商店。

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

如果不存在这样的城市，则输出 $-1$。

输入格式

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

第二行包含 $k$ 个整数，表示有动漫商店的城市编号。

接下来 $m$ 行，每行包含两个整数 $a,b$，表示城市 $a$ 和城市 $b$ 之间有一条双向道路。

输出格式

输出 $n$ 个整数。第 $i$ 个整数表示从城市 $i$ 出发，到另一座有动漫商店的城市的最短距离。

如果不存在这样的城市，则输出 $-1$。

样例

输入

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

数据范围

子任务 1（23 分）

• $1 \le k \le n \le 1000$
• $0 \le m \le 2000$

子任务 2（16 分）

• $1 \le k \le n \le 10^5$
• $m=n-1$
• 每条道路都连接城市 $i$ 和 $i+1$，其中 $i=1,2,\dots,n-1$

子任务 3（61 分）

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