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

서브태스크

힌트