多源最短路径题目

题目描述

在一个城市地图上，存在 (N) 个地点（编号为 \(1, 2, \dots, N\)），以及 (M) 条道路。每条道路是双向的，连接两个地点，并且所有道路的长度相同（边权为 1）。

有多个避难所（源点），你需要从这些避难所出发，计算到每个地点的最短距离。所有避难所的位置已经给出，你需要通过多源最短路径的算法，找到从这些避难所到每个地点的最短距离。

输入格式

• 第一行包含两个整数 (N) 和 (M)（\(2 \leq N \leq 10^5\), \(N - 1 \leq M \leq 10^5\)），表示地点数和道路数。
• 接下来的 (M) 行，每行包含两个整数 \(A_i\) 和 \(B_i\) \(1 \leq A_i < B_i \leq N\)，表示地点 \(A_i\) 和 \(B_i\) 之间有一条双向道路。
• 第 (M + 1) 行包含一个整数 (K)（\(1 \leq K \leq N\)），表示有 (K) 个避难所。
• 第 (M + 2) 行包含 (K) 个整数 (\(S_1, S_2, \dots, S_K\))，表示避难所的位置，\(S_i\) 是避难所的编号。

输出格式

输出 (N) 行，每行包含一个整数，表示从任一避难所到该地点的最短距离。如果某个地点无法从任何一个避难所到达，输出 \(-1\)。

示例

输入示例 1：

5 5
1 2
1 3
2 3
3 4
4 5
2
1 5

输出示例 1：

0
1
1
1
1

输入示例 2：

4 3
1 2
2 3
3 4
2
1 3

输出示例 2：

0
1
0
1