P10433 [JOIST 2024] 棋盘游戏 / Board Game

有一个供 $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$ 上所需的最小总移动次数。

#### 样例解释 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 分) 没有额外的约束。