题目描述

有一个供 $K$ 个玩家玩的棋盘游戏。该游戏的棋盘由 $N$ 个编号从 1 到 $N$ 的单元格和 $M$ 条编号从 1 到 $M$ 的路径组成，其中路径 $j$（$1 ≤ j ≤ M$）双向连接着单元格 $U_j$ 和 $V_j$。

棋盘上有两种类型的单元格：重新激活单元格和停止单元格。

这些信息由长度为 $N$ 的字符串 $S$ 给出，$S$ 由 $0$ 和 $1$ 组成，其中 $S$ 的第 $i$ 个字符（$1 ≤ i ≤ N$）是 '0' 表示单元格 $i$ 是重新激活单元格，是 '1' 表示单元格 $i$ 是停止单元格。

这个棋盘游戏由编号从 $1$ 到 $K$ 的 $K$ 个玩家进行。每个玩家都有自己的棋子，游戏从每个玩家将其棋子放在特定的单元格上开始。一开始，玩家 $p$（$1 \leq p \leq K$）将其棋子放在单元格 $X_p$ 上。注意，多个玩家的棋子可以放在同一个单元格上。

游戏随着每个玩家轮流进行而进行，从玩家 1 开始，按数字顺序进行。在玩家 $p$ 完成其回合后，玩家 $p + 1$ 开始回合（如果 $p = K$，则玩家 1 开始回合）。每个玩家在其回合上执行以下操作：

1. 选择与其棋子所在的单元格通过一条路径相连的一个单元格，并将其棋子移动到所选择的单元格上。
2. 如果目标单元格是重新激活单元格，则重复步骤 1 并继续其回合。如果目标单元格是停止单元格，则结束其回合。

代表日本参加这个棋盘游戏的包括 JOI 君在内的由 $K$ 名成员组成的团队，正在研究协作策略，以快速征服这个游戏。他们目前正在研究以下问题：

为了将玩家 1 的棋子放置在单元格 $T$ 上，$K$ 名玩家需要的最小总移动次数是多少？即使在回合中途，如果玩家 1 的棋子被放置在单元格 $T$ 上，也认为满足条件。

给定关于游戏棋盘和每个玩家棋子的初始放置位置的信息，编写一个程序来计算每个 $T = 1, 2, \ldots, N$ 对应的问题的答案。

输入格式

从标准输入中读取以下数据：

• $N$ $M$ $K$
• $U_1$ $V_1$
• $U_2$ $V_2$
• ...
• $U_M$ $V_M$
• $S$
• $X_1,X_2,...,X_K$

输出格式

输出 $N$ 行。在第 $T$ 行（$1 ≤ T ≤ N$）上，输出 $K$ 个玩家将玩家 1 的棋子放在单元格 $T$ 上所需的最小总移动次数。

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

0
1
2
2
3

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

0
1
4
4
5

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

0
1
3
3
4

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

4
2
3
0
10
1
17
24

12 13 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
2 9
7 12
11 12
110000011101
1 9 11

0
1
4
5
6
7
8
8
4
1
13
9

提示

样例解释 1

由于玩家 $1$ 的棋子从单元格 $1$ 开始，所以 $T = 1$ 的答案是 $0$。

对于 $T = 2$，在第一步中，玩家 $1$ 可以将他的棋子从单元格 $1$ 移动到单元格 $2$。因此，$T = 2$ 的答案是 $1$。

对于 $T = 3$，他们可以通过以下 $2$ 步将玩家 $1$ 的棋子放置在单元格 $3$ 上：

• 在第一步中，玩家 $1$ 将他的棋子从单元格 $1$ 移动到单元格 $2$。由于单元格 $2$ 是一个激活单元格，因此玩家 $1$ 的回合继续。
• 在第二步中，玩家 $1$ 将他的棋子从单元格 $2$ 移动到单元格 $3$。

由于他们无法在 $1$ 步或更少的步骤中将玩家 $1$ 的棋子放置在单元格 $3$ 上，所以 $T = 3$ 的答案是 $2$。

类似地，可以验证 $T = 4$ 的答案为 $2$，$T = 5$ 的答案为 $3$。

这个样例输入满足子任务 $1,4,5,6,7,8$ 的约束。

样例解释 2

对于 $T = 3$，他们可以通过以下 4 步将玩家 $1$ 的棋子放置在单元格 $3$ 上：

• 在第一步中，玩家 $1$ 将他的棋子从单元格 $1$ 移动到单元格 $2$。由于单元格 $2$ 是一个停止单元格，接下来轮到玩家 $2$。
• 在第二步中，玩家 $2$ 将他的棋子从单元格 $5$ 移动到单元格 $3$。由于单元格 $3$ 是一个激活单元格，玩家 $2$ 的回合继续。
• 在第三步中，玩家 $2$ 将他的棋子从单元格 $3$ 移动到单元格 $2$。由于单元格 $2$ 是一个停止单元格，接下来轮到玩家 $1$。
• 在第四步中，玩家 $1$ 将他的棋子从单元格 $2$ 移动到单元格 $3$。

由于他们无法在 $3$ 步或更少的步骤中将玩家 $1$ 的棋子放置在单元格 $3$ 上，所以 $T = 3$ 的答案是 $4$。

这个样例输入满足子任务 $2,4,5,6,7,8$ 的约束。

样例解释 3

这个样例输入满足子任务 $3, 4, 5, 6, 7,8$ 的约束。

样例解释 4

这个样例输入满足子任务 $4, 6, 7,8$ 的约束。

样例解释 5

这个样例输入满足子任务 $4, 6, 7,8$ 的约束。

约束条件

• $2 \leq N \leq 50,000$
• $1 \leq M \leq 50,000$
• $2 \leq K \leq 50,000$
• $1 \leq U_j < V_j \leq N$（$1 \leq j \leq M$）
• $(U_j, V_j)$，$(U_k, V_k)$（$1 \leq j < k \leq M$）
• 可以通过经过多条路径从任何单元格到达任何其他单元格。
• $S$ 是长度为 $N$ 的由 '0' 和 '1' 组成的字符串。
• $1 \leq X_p \leq N$（$1 \leq p \leq K$）
• $N$、$M$ 和 $K$ 都是整数。
• $U_j$ 和 $V_j$ 是整数（$1 \leq j \leq M$）。
• $X_p$ 是整数（$1 \leq p \leq K$）。

子任务

1. (3 分) 没有终止单元格。
2. (7 分) 恰好有一个终止单元格。
3. (7 分) 恰好有两个终止单元格。
4. (19 分) $N \leq 3,000$，$M \leq 3,000$，$K \leq 3,000$
5. (23 分) $K = 2$
6. (9 分) $K \leq 100$
7. (23 分) $N \leq 30,000$，$M \leq 30,000$，$K \leq 30,000$
8. (9 分) 没有额外的约束。