{"raw_statement":[{"iden":"statement","content":"有一个供 $K$ 个玩家玩的棋盘游戏。该游戏的棋盘由 $N$ 个编号从 1 到 $N$ 的单元格和 $M$ 条编号从 1 到 $M$ 的路径组成，其中路径 $j$（$1 ≤ j ≤ M$）双向连接着单元格 $U_j$ 和 $V_j$。\n\n棋盘上有两种类型的单元格：重新激活单元格和停止单元格。\n\n这些信息由长度为 $N$ 的字符串 $S$ 给出，$S$ 由 $0$ 和 $1$ 组成，其中 $S$ 的第 $i$ 个字符（$1 ≤ i ≤ N$）是 '0' 表示单元格 $i$ 是重新激活单元格，是 '1' 表示单元格 $i$ 是停止单元格。\n\n这个棋盘游戏由编号从 $1$ 到 $K$ 的 $K$ 个玩家进行。每个玩家都有自己的棋子，游戏从每个玩家将其棋子放在特定的单元格上开始。一开始，玩家 $p$（$1 \\leq p \\leq K$）将其棋子放在单元格 $X_p$ 上。注意，多个玩家的棋子可以放在同一个单元格上。\n\n游戏随着每个玩家轮流进行而进行，从玩家 1 开始，按数字顺序进行。在玩家 $p$ 完成其回合后，玩家 $p + 1$ 开始回合（如果 $p = K$，则玩家 1 开始回合）。每个玩家在其回合上执行以下操作：\n\n1. 选择与其棋子所在的单元格通过一条路径相连的一个单元格，并将其棋子移动到所选择的单元格上。\n2. 如果目标单元格是重新激活单元格，则重复步骤 1 并继续其回合。如果目标单元格是停止单元格，则结束其回合。\n\n代表日本参加这个棋盘游戏的包括 JOI 君在内的由 $K$ 名成员组成的团队，正在研究协作策略，以快速征服这个游戏。他们目前正在研究以下问题：\n\n为了将玩家 1 的棋子放置在单元格 $T$ 上，$K$ 名玩家需要的最小总移动次数是多少？即使在回合中途，如果玩家 1 的棋子被放置在单元格 $T$ 上，也认为满足条件。\n\n给定关于游戏棋盘和每个玩家棋子的初始放置位置的信息，编写一个程序来计算每个 $T = 1, 2, \\ldots, N$ 对应的问题的答案。"},{"iden":"input","content":"从标准输入中读取以下数据：\n\n- $N$ $M$ $K$\n- $U_1$ $V_1$\n- $U_2$ $V_2$\n- ...\n- $U_M$ $V_M$\n- $S$\n- $X_1,X_2,...,X_K$\n"},{"iden":"output","content":"输出 $N$ 行。在第 $T$ 行（$1 ≤ T ≤ N$）上，输出 $K$ 个玩家将玩家 1 的棋子放在单元格 $T$ 上所需的最小总移动次数。\n"},{"iden":"note","content":"#### 样例解释 1\n\n由于玩家 $1$ 的棋子从单元格 $1$ 开始，所以 $T = 1$ 的答案是 $0$。\n\n对于 $T = 2$，在第一步中，玩家 $1$ 可以将他的棋子从单元格 $1$ 移动到单元格 $2$。因此，$T = 2$ 的答案是 $1$。\n\n对于 $T = 3$，他们可以通过以下 $2$ 步将玩家 $1$ 的棋子放置在单元格 $3$ 上：\n\n- 在第一步中，玩家 $1$ 将他的棋子从单元格 $1$ 移动到单元格 $2$。由于单元格 $2$ 是一个激活单元格，因此玩家 $1$ 的回合继续。\n- 在第二步中，玩家 $1$ 将他的棋子从单元格 $2$ 移动到单元格 $3$。\n\n由于他们无法在 $1$ 步或更少的步骤中将玩家 $1$ 的棋子放置在单元格 $3$ 上，所以 $T = 3$ 的答案是 $2$。\n\n类似地，可以验证 $T = 4$ 的答案为 $2$，$T = 5$ 的答案为 $3$。\n\n这个样例输入满足子任务 $1,4,5,6,7,8$ 的约束。\n\n\n\n#### 样例解释 2\n\n对于 $T = 3$，他们可以通过以下 4 步将玩家 $1$ 的棋子放置在单元格 $3$ 上：\n\n- 在第一步中，玩家 $1$ 将他的棋子从单元格 $1$ 移动到单元格 $2$。由于单元格 $2$ 是一个停止单元格，接下来轮到玩家 $2$。\n- 在第二步中，玩家 $2$ 将他的棋子从单元格 $5$ 移动到单元格 $3$。由于单元格 $3$ 是一个激活单元格，玩家 $2$ 的回合继续。\n- 在第三步中，玩家 $2$ 将他的棋子从单元格 $3$ 移动到单元格 $2$。由于单元格 $2$ 是一个停止单元格，接下来轮到玩家 $1$。\n- 在第四步中，玩家 $1$ 将他的棋子从单元格 $2$ 移动到单元格 $3$。\n\n由于他们无法在 $3$ 步或更少的步骤中将玩家 $1$ 的棋子放置在单元格 $3$ 上，所以 $T = 3$ 的答案是 $4$。\n\n这个样例输入满足子任务 $2,4,5,6,7,8$ 的约束。\n\n#### 样例解释 3\n\n这个样例输入满足子任务 $3, 4, 5, 6, 7,8$ 的约束。\n\n#### 样例解释 4\n\n这个样例输入满足子任务 $4, 6, 7,8$ 的约束。\n\n#### 样例解释 5\n\n这个样例输入满足子任务 $4, 6, 7,8$ 的约束。\n\n### 约束条件\n\n- $2 \\leq N \\leq 50,000$\n- $1 \\leq M \\leq 50,000$\n- $2 \\leq K \\leq 50,000$\n- $1 \\leq U_j < V_j \\leq N$（$1 \\leq j \\leq M$）\n- $(U_j, V_j)$，$(U_k, V_k)$（$1 \\leq j < k \\leq M$）\n- 可以通过经过多条路径从任何单元格到达任何其他单元格。\n- $S$ 是长度为 $N$ 的由 '0' 和 '1' 组成的字符串。\n- $1 \\leq X_p \\leq N$（$1 \\leq p \\leq K$）\n- $N$、$M$ 和 $K$ 都是整数。\n- $U_j$ 和 $V_j$ 是整数（$1 \\leq j \\leq M$）。\n- $X_p$ 是整数（$1 \\leq p \\leq K$）。\n\n### 子任务\n\n1. (3 分) 没有终止单元格。\n2. (7 分) 恰好有一个终止单元格。\n3. (7 分) 恰好有两个终止单元格。\n4. (19 分) $N \\leq 3,000$，$M \\leq 3,000$，$K \\leq 3,000$\n5. (23 分) $K = 2$\n6. (9 分) $K \\leq 100$\n7. (23 分) $N \\leq 30,000$，$M \\leq 30,000$，$K \\leq 30,000$\n8. (9 分) 没有额外的约束。\n\n"}],"translated_statement":null,"sample_group":[["5 5 2\n1 2\n2 3\n2 4\n3 5\n4 5\n00000\n1 5","0\n1\n2\n2\n3"],["5 5 2\n1 2\n2 3\n2 4\n3 5\n4 5\n01000\n1 5","0\n1\n4\n4\n5"],["5 5 2\n1 2\n2 3\n2 4\n3 5\n4 5\n01100\n1 5\n","0\n1\n3\n3\n4"],["8 7 5\n1 3\n5 7\n4 6\n2 6\n2 3\n7 8\n1 5\n10011010\n4 6 4 7 1","4\n2\n3\n0\n10\n1\n17\n24"],["12 13 3\n1 2\n2 3\n3 4\n4 5\n5 6\n6 7\n7 8\n8 9\n9 10\n1 10\n2 9\n7 12\n11 12\n110000011101\n1 9 11\n","0\n1\n4\n5\n6\n7\n8\n8\n4\n1\n13\n9"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}