Problem Description

There is a board game played by $K$ players. The board consists of $N$ cells numbered from $1$ to $N$ and $M$ paths numbered from $1$ to $M$. Path $j$ ($1 \le j \le M$) connects cell $U_j$ and cell $V_j$ in both directions.

There are two types of cells on the board: reactivating cells and stopping cells.

This information is given by a string $S$ of length $N$. $S$ consists of $0$ and $1$. The $i$-th character of $S$ ($1 \le i \le N$) is '0' if cell $i$ is a reactivating cell, and '1' if cell $i$ is a stopping cell.

This board game is played by $K$ players numbered from $1$ to $K$. Each player has their own piece, and the game starts with each player placing their piece on a specific cell. Initially, player $p$ ($1 \leq p \leq K$) places their piece on cell $X_p$. Note that multiple players' pieces may be on the same cell.

The game proceeds with the players taking turns, starting from player $1$ and continuing in numerical order. After player $p$ finishes their turn, player $p + 1$ starts their turn (if $p = K$, then player $1$ starts their turn). On their turn, each player performs the following:

1. Choose a cell connected to the cell where their piece currently is by a path, and move their piece to the chosen cell.
2. If the destination cell is a reactivating cell, repeat step 1 and continue their turn. If the destination cell is a stopping cell, end their turn.

A team of $K$ members representing Japan in this board game, including JOI-kun, is studying cooperative strategies to conquer this game quickly. They are currently studying the following question:

What is the minimum total number of moves needed by the $K$ players to place player $1$'s piece on cell $T$? Even if player $1$'s piece is placed on cell $T$ in the middle of a turn, it is considered successful.

Given the information about the game board and the initial positions of each player's piece, write a program to compute the answer to the above question for each $T = 1, 2, \ldots, N$.

Input Format

Read the following data from standard input:

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

Output Format

Output $N$ lines. On line $T$ ($1 \le T \le N$), output the minimum total number of moves required for the $K$ players to place player $1$'s piece on cell $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

Hint

Sample Explanation 1

Since player $1$'s piece starts from cell $1$, the answer for $T = 1$ is $0$.

For $T = 2$, in the first move, player $1$ can move their piece from cell $1$ to cell $2$. Therefore, the answer for $T = 2$ is $1$.

For $T = 3$, they can place player $1$'s piece on cell $3$ in the following $2$ moves:

• In the first move, player $1$ moves their piece from cell $1$ to cell $2$. Since cell $2$ is a reactivating cell, player $1$'s turn continues.
• In the second move, player $1$ moves their piece from cell $2$ to cell $3$.

Since they cannot place player $1$'s piece on cell $3$ in $1$ move or less, the answer for $T = 3$ is $2$.

Similarly, it can be verified that the answer for $T = 4$ is $2$, and the answer for $T = 5$ is $3$.

This sample input satisfies the constraints of subtasks $1, 4, 5, 6, 7, 8$.

Sample Explanation 2

For $T = 3$, they can place player $1$'s piece on cell $3$ in the following $4$ moves:

• In the first move, player $1$ moves their piece from cell $1$ to cell $2$. Since cell $2$ is a stopping cell, it is then player $2$'s turn.
• In the second move, player $2$ moves their piece from cell $5$ to cell $3$. Since cell $3$ is a reactivating cell, player $2$'s turn continues.
• In the third move, player $2$ moves their piece from cell $3$ to cell $2$. Since cell $2$ is a stopping cell, it is then player $1$'s turn.
• In the fourth move, player $1$ moves their piece from cell $2$ to cell $3$.

Since they cannot place player $1$'s piece on cell $3$ in $3$ moves or less, the answer for $T = 3$ is $4$.

This sample input satisfies the constraints of subtasks $2, 4, 5, 6, 7, 8$.

Sample Explanation 3

This sample input satisfies the constraints of subtasks $3, 4, 5, 6, 7, 8$.

Sample Explanation 4

This sample input satisfies the constraints of subtasks $4, 6, 7, 8$.

Sample Explanation 5

This sample input satisfies the constraints of subtasks $4, 6, 7, 8$.

Constraints

• $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$) are distinct.
• It is possible to reach any cell from any other cell by traversing one or more paths.
• $S$ is a string of length $N consisting of '0' and '1'.
• $1 \leq X_p \leq N$ ($1 \leq p \leq K$)
• $N$, $M$, and $K$ are integers.
• $U_j$ and $V_j$ are integers ($1 \leq j \leq M$).
• $X_p$ is an integer ($1 \leq p \leq K$).

Subtasks

1. (3 points) There are no stopping cells.
2. (7 points) There is exactly one stopping cell.
3. (7 points) There are exactly two stopping cells.
4. (19 points) $N \leq 3,000$, $M \leq 3,000$, $K \leq 3,000$
5. (23 points) $K = 2$
6. (9 points) $K \leq 100$
7. (23 points) $N \leq 30,000$, $M \leq 30,000$, $K \leq 30,000$
8. (9 points) No additional constraints.

Translated by ChatGPT 5