31729번 - Board Game 서브태스크다국어

There is a board game for $K$ players. The board of this game consists of $N$ cells numbered from $1$ to $N$, and $M$ paths numbered from $1$ to $M$, where path $j$ ($1 ≤ j ≤ M$) connects cells $U_j$ and $V_j$ bidirectionally.

There are two types of cells on the board: re-activate cells and stop cells.

This information is given by a string $S$ of length $N$ consisting of '0' and '1’, where the $i$-th character of $S$ ($1 ≤ i ≤ N$) is '0' if cell $i$ is a re-activate cell, and '1' if cell $i$ is a stop 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 specified cell. At the beginning, player $p$ ($1 ≤ p ≤ K$) places their piece on cell $X_p$. Note that multiple players’ pieces can be placed on the same cell.

The game progresses with each player taking turns starting from player $1$ and proceeding in numerical order. After player $p$ finishes their turn, the turn moves to player $p + 1$ (if $p = K$, then the turn goes to player $1$). Each player takes the following actions on their turn:

1. Choose one cell connected to the cell where their piece is placed via a path, and move their piece to the chosen cell.
2. If the destination cell is a re-activate cell, repeat step 1 and continue their turn. If the destination cell is a stop cell, end their turn.

The team consisting of $K$ members, including JOI-Kun, who represent Japan in this board game, are researching cooperative strategies to quickly conquer the game. They are currently studying the following problem:

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

Given the information about the board of the game and the initial placement of each player’s piece, create a program to calculate the answer to this problem for each $T = 1, 2, \dots , N$.

Read the following data from the standard input.

$N$ $M$ $K$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_M$ $V_M$

$S$

$X_1$ $X_2$ $\cdots$ $X_K$

Output $N$ lines to the standard output. On the $T$-th line ($1 ≤ T ≤ N$), output the minimum total number of moves required by the $K$ players to place player $1$’s piece on cell $T$.

• $2 ≤ N ≤ 50\, 000$.
• $1 ≤ M ≤ 50\, 000$.
• $2 ≤ K ≤ 50\, 000$.
• $1 ≤ U_j < V_j ≤ N$ ($1 ≤ j ≤ M$).
• $(U_j , V_j) \ne (U_k, V_k)$ ($1 ≤ j < k ≤ M$).
• It is possible to reach any cell from any other cell by traversing several paths.
• $S$ is a string of length $N$ consisting of '0' and '1'.
• $1 ≤ X_p ≤ N$ ($1 ≤ p ≤ K$).
• $N$, $M$ and $K$ are integers.
• $U_j$ and $V_j$ are integers ($1 ≤ j ≤ M$).
• $X_p$ is an integer ($1 ≤ p ≤ K$).