P10433 [JOIST 2024] Board Game

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

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

#### 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