题目描述

题目译自 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$ 步；若选择的为停止格，该回合停止。

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

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

输入格式

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

$N$ $M$ $K$ $U1$ $V1$

$​U2$ $V2$

$​⋮$

$UM$ $VM$ ​ $S$

$X1$ $X2$ $​⋯$ $XK$ ​

输出格式

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

样例1：

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$ 的限制。

样例2：

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$ 的限制。 样例3：

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$ 的限制。

样例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

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

样例5：

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)$

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

col
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