3905 - 社区超市

题目描述

某地区有 N 个小区(编号为 1N),有 M双向的道路连接这些小区,每条道路连接了两个不同的小区N 个小区通过 M 条双向道路连接成为了一个大型社区,社区中任意两个小区都可以通过 1 条或多条道路相连。

其中有 K 个小区中建有社区超市,第 i 个超市建在编号为 C_i 的小区,每个小区中最多建有 1社区超市。

请编程求解出,对于社区中的每个小区中的居民,到最近的社区超市,最少要经过多少条道路?

输入

1 行包含三个整数 NMK,分别表示小区数量、道路数量以及社区超市数量。

2 行包含 K 个整数,表示建有社区超市的小区编号。

接下来 M 行,每行包含两个整数 uv,表示小区 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 1000M \le 2000K=1

对于 60\% 的数据,满足 N \le 10000M \le 20000

对于 100\% 的数据,满足 1 \le N \le 10^51 \le N-1 \le M \le 10^51 \le K \le N1 \le C_i \le N \le u \neq v \le N

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 基础


上一题 下一题