题目描述

题目译自 JOISC 2024 Day2 T1 「ボードゲーム / Board Game」

给定一个 $N$ 个格子，$M$ 条无向边的棋盘，其中边 $j(1\le j\le M)$ 连接格子 $U_j$ 和 $V_j$。所有格子分为两类：激活格和停止格。格子信息用一个字符串 $S$ 表示，若 $S$ 第 $i$ 位（$1\le i\le N$）为 0，则格子 $i$ 为激活格，若 $S$ 第 $i$ 位（$1\le i\le N$）为 1，则格子 $i$ 为停止格。

总共有 $K$ 个玩家，编号从 $1$ 到 $K$。每个玩家有一枚棋子，初始时各有一个固定起点，其中玩家 $p(1\le p\le K)$ 的棋子放置于格子 $X_p$。多个玩家的棋子起点可能相同。

从玩家 1 开始，每个玩家按编号顺序轮流移动棋子。玩家 $p$ 的回合之后是玩家 $p+1$ 的回合（若 $p=K$，则之后是玩家 $1$ 的回合）。每个玩家在自己的回合内：

1. 选择一个与该玩家的棋子所在格子有边直接相连的格子，并将棋子移动到该格。
2. 若选择的目标格是激活格，重复第 1 步；若选择的为停止格，该回合停止。

JOI 君希望知道：要使玩家 1 的棋子移动到格子 $T$，所有玩家的棋子共需要移动多少步？若玩家 1 的棋子在回合中途位于格子 $T$，同样满足条件，从而立即结束游戏。

对 $1,2,\cdots N$ 中每个 $T$，求出答案。

输入格式

从标准输入读入以下内容：

$$\begin{align} & N\enspace M\enspace K \\ & U_1\enspace V_1 \\ & U_2\enspace V_2 \\ & \vdots \\ & U_M\enspace V_M \\ & S \\ & X_1\enspace X_2\enspace \cdots X_K \end{align} $$

输出格式

$N$ 行各一个整数，其中第 $T$ 行（$1\le T\le N$）表示使玩家 1 的棋子移动到格子 $T$ 所需的 $K$ 个玩家总步数的最小值。

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

0
1
2
2
3

玩家 1 的棋子初始位于格子 $1$，因此 $T=1$ 对应答案为 $0$。

对于 $T=2$，玩家 1 第一步将棋子从格子 $1$ 移动到格子 $2$，答案为 $1$。

对于 $T=3$，玩家先将棋子从格子 $1$ 移动到格子 $2$；由于格子 $2$ 是激活格，玩家可以继续将棋子从格子 $2$ 移动到格子 $3$。

由于无法用不超过 1 步将玩家 1 的棋子移动到格子 $3$，$T=3$ 对应答案为 $2$。

类似地，容易证明，$T=4$ 对应答案为 $2$，$T=5$ 对应答案为 $3$。

这组样例满足子任务 $1,\,4,\,5,\,6,\,7,\,8$ 的限制。

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

0
1
4
4
5

对于 $T=3$，至少需要 4 步：

• 第一步，玩家 1 将棋子从格子 $1$ 移动到格子 $2$，格子 $2$ 为停止格，玩家 1 回合结束。
• 第二步，玩家 2 将棋子从格子 $5$ 移动到格子 $3$，格子 $3$ 为激活格，玩家 2 回合继续。
• 第三步，玩家 2 将棋子从格子 $3$ 移动到格子 $2$，格子 $2$ 为停止格，玩家 2 回合结束。
• 第四步，玩家 1 将棋子从格子 $2$ 移动到格子 $3$。

无法用不超过 3 步达成目标，因此 $T=3$ 对应答案为 $4$.

这组样例满足子任务 $2,\,4,\,5,\,6,\,7,\,8$ 的限制。

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

0
1
3
3
4

这组样例满足子任务 $3,\,4,\,5,\,6,\,7,\,8$ 的限制。

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

这组样例满足子任务 $4,\,6,\,7,\,8$ 的限制。

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

这组样例满足子任务 $4,\,6,\,7,\,8$ 的限制。

数据范围与提示

对于所有数据，满足：

• $2\le N\le 50\,000$
• $1\le M\le 50\,000$
• $2\le K\le 50\,000$
• $1\le U_j\le V_j\le N(1\le j\le M)$
• $(U_j,V_j)\neq (U_k,V_k)(1\le j<k\le M)$
• 从任何一个格子出发，经过若干条边，可以到达任意其他格子
• 字符串 $S$ 长度为 $N$ 且仅包含 0 和 1
• $1\le X_p\le N$（$1\le p\le K$）
• $N,M,K$ 为整数
• $U_j,V_j$ 为整数（$1\le j\le M$）
• $X_p$ 为整数（$1\le p\le K$）

详细子任务附加限制及分值如下表所示：

子任务编号	附加限制	分值
$1$	没有停止格	$3$
$2$	恰好有一个停止格	$7$
$3$	恰好有两个停止格
$4$	$N,M,K\le 3\,000$	$19$
$5$	$K\le 2$	$23$
$6$	$K\le 100$	$9$
$7$	$N,M,K\le 30\,000$	$23$
$8$	无附加限制	$9$