Minimum Moves to Reach Target Cell in a Cooperative Board Game

A board game is played by \(K\) players on a board consisting of \(N\) cells numbered from \(1\) to \(N\) and \(M\) bidirectional paths. Each path \(j\) (\(1 \leq j \leq M\)) connects two cells \(U_j\) and \(V_j\).

Each cell is either a reactivating cell or a stopping cell. A binary string \(S\) of length \(N\) is given where the \(i\)th character is '0' if cell \(i\) is a reactivating cell and '1' if it is a stopping cell.

The game begins with each player \(p\) (\(1 \leq p \leq K\)) placing their piece on cell \(X_p\). Note that multiple pieces can share the same cell.

The players take turns in a cyclic order starting from player 1. In each turn, the active player follows these steps:

1. From the cell where the player’s piece is currently located, select an adjacent cell (i.e. one connected by a path) and move the piece to that cell.
2. If the destination cell is a reactivating cell (i.e. its corresponding character in \(S\) is '0'), the player must immediately continue by choosing another adjacent cell and moving there. If the destination cell is a stopping cell (i.e. its corresponding character in \(S\) is '1'), the turn ends.

The goal is to determine, for every target cell \(T\) (\(1 \leq T \leq N\)), the minimum total number of moves required (by all players combined) so that player 1’s piece is placed on cell \(T\) at some moment. Note that if player 1 reaches \(T\) in the middle of his turn, even before the forced continuation from a reactivating cell, it is considered successful.

Insight: With fully cooperative play and control over each move, the optimal strategy is to have player 1 move on his very first turn along a path from \(X_1\) to \(T\) using as few moves as possible. In other words, the answer for each target \(T\) is simply the shortest distance from \(X_1\) to \(T\) in an undirected unweighted graph (with the twist that if \(T = X_1\) then the cost is 0). If \(T\) is unreachable, output \(-1\).

inputFormat

The input consists of multiple lines:

• The first line contains three integers \(N\), \(M\), and \(K\) (\(1 \leq N, M, K \leq 2 \times 10^5\)).
• The second line contains a binary string \(S\) of length \(N\): the \(i\)th character is '0' if cell \(i\) is a reactivating cell and '1' if it is a stopping cell.
• Then follow \(M\) lines, each containing two integers \(U_j\) and \(V_j\) (\(1 \leq U_j, V_j \leq N\)), representing a bidirectional path between cells \(U_j\) and \(V_j\).
• The next line contains \(K\) integers \(X_1, X_2, \ldots, X_K\), indicating the initial positions of players 1 through \(K\).

outputFormat

Output \(N\) space-separated integers. The \(T\)th integer (for \(1 \leq T \leq N\)) is the minimum total number of moves required for player 1’s piece to be placed on cell \(T\). If it is impossible to achieve for a particular \(T\), output \(-1\) for that target.

sample

5 5 2
01010
1 2
2 3
3 4
4 5
2 5
1 3

0 1 2 2 3