The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 2 – Board Game

ボードゲーム (Board Game)

K 人用のボードゲームがある．このボードゲームのボードには 1 から N までの番号のついた N 個のマスと，1 から M までの番号のついた M 本の道があり，道 j (1 ≦ j ≦ M) はマス U j と V j の間を双方向に接続している．

N 個のマスには再行動マスと停止マスとの 2 種類がある．その情報は ‘0’, ‘1’ からなる長さ N の文字列
S によって与えられ，S の i 文字目 (1 ≦ i ≦ N) が ‘0’ ならばマス i は再行動マス，S の i 文字目が ‘1’ ならばマス i は停止マスである．
このボードゲームは 1 から K までの番号がついた K 人のプレイヤーで遊ぶ．各プレイヤーは自分の駒を1 つ持っており，各プレイヤーの駒を指定されたマスの上に置いてゲームを開始する．はじめプレイヤー p(1 ≦ p ≦ K) の駒はマス X p に置く．なお，1 つのマスに複数のプレイヤーの駒を置くことも可能である．
ゲームはプレイヤー 1 から始めて番号順に自分のターンをプレイするという形で進行する．プレイヤー pが自分のターンをプレイし終わると，次はプレイヤー p + 1 （ただし p = K ならばプレイヤー 1）のターンとなる．各プレイヤーは，自分のターンのときに次のような行動を行う：

1. 自分の駒が置かれているマスと道で接続されているマスをひとつ選び，選んだマスに自分の駒を移動させる．

2. 移動先のマスが再行動マスならば 1. に戻り，自分のターンを継続する．移動先のマスが停止マスならば自分のターンを終了する．
このボードゲームの日本代表である JOI 君たち K 人は，ゲームを協力して高速に攻略する方法を研究している．現在研究しているのは次の問題である：
プレイヤー 1 の駒がマス T に置かれている状態にするために必要な，K 人合計での駒の移動回数の最小値はいくつか．なお，ターンの途中であっても，プレイヤー 1 の駒がマス T に置かれれば条件が満たされたものとみなす．
ボードゲームのボードの情報と各プレイヤーの駒の初期配置が与えられた場合に，各 T = 1, 2, . . . , N に対して，この問題の答えを計算するプログラムを作成せよ．

ボードゲーム– 1 / 5

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 2 – Board Game

入力
入力は以下の形式で標準入力から与えられる．

NMK
U1 V1
U2 V2..
.
U M VMS
X1 X2 · · · XK

出力
標準出力に N 行出力せよ．T 行目 (1 ≦ T ≦ N) には，プレイヤー 1 の駒がマス T に置かれている状態にするために必要な，K 人合計での駒の移動回数の最小値を出力せよ．

制約• 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 ) , (Uk , Vk ) (1 ≦ j < k ≦ M)．
• どのマスからどのマスへも，結ばれている道を何本か辿って到達できる．
• S は ‘0’, ‘1’ からなる長さ N の文字列である．
• 1 ≦ X p ≦ N (1 ≦ p ≦ K)．
• N, M, K は整数である．
• U j , V j は整数である (1 ≦ j ≦ M)．
• X p は整数である (1 ≦ p ≦ K)．

ボードゲーム– 2 / 5

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 2 – Board Game小課題
1. (3 点) 停止マスは存在しない．
2. (7 点) 停止マスの個数は 1 個である．
3. (7 点) 停止マスの個数は 2 個である．
4. (19 点) N ≦ 3 000， M ≦ 3 000，K ≦ 3 000．
5. (23 点) K = 2．
6. (9 点) K ≦ 100．
7. (23 点) N ≦ 30 000， M ≦ 30 000，K ≦ 30 000．
8. (9 点) 追加の制約はない．

入出力例
入力例 1

出力例 15 5 201 212 322 423 534 500000
1 5
はじめプレイヤー 1 の駒はマス 1 に置かれているので，T = 1 に対する答えは 0 である．

T = 2 のとき，1 回目の移動で，プレイヤー 1 の駒をマス 1 からマス 2 に移動させることができる．した
がって T = 2 に対する答えは 1 である．

T = 3 のとき，次のような 2 回の移動でプレイヤー 1 の駒をマス 3 に置くことができる．
• 1 回目の移動では，プレイヤー 1 の駒をマス 1 からマス 2 に移動させる．マス 2 は再行動マスであるから，プレイヤー 1 のターンが継続される．

• 2 回目の移動では，プレイヤー 1 の駒をマス 2 からマス 3 に移動させる．
1 回以下の移動でプレイヤー 1 の駒をマス 3 に置くことはできないため，T = 3 に対する答えは 2 である．
同様に T = 4 に対する答えは 2，T = 5 に対する答えは 3 であることが確かめられる．
この入力例は小課題 1, 4, 5, 6, 7, 8 の制約を満たす．

ボードゲーム– 3 / 5

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying TrialMarch 20–24, 2024 (Komaba, Tokyo)
Contest 2 – Board Game

入力例 2出力例 25 5 20

1 2

12 342 443 5

54 501000
1 5
例えば T = 3 のとき，次のような 4 回の移動でプレイヤー 1 の駒をマス 3 に置くことができる．

• 1 回目の移動では，プレイヤー 1 の駒をマス 1 からマス 2 に移動させる．マス 2 は停止マスであるから，次はプレイヤー 2 のターンとなる．

• 2 回目の移動では，プレイヤー 2 の駒をマス 5 からマス 3 に移動させる．マス 3 は再行動マスであるから，プレイヤー 2 のターンが継続される．

• 3 回目の移動では，プレイヤー 2 の駒をマス 3 からマス 2 に移動させる．マス 2 は停止マスであるから，次はプレイヤー 1 のターンとなる．

• 4 回目の移動では，プレイヤー 1 の駒をマス 2 からマス 3 に移動させる．
3 回以下の移動でプレイヤー 1 の駒をマス 3 に置くことはできないため，T = 3 に対する答えは 4 である．
この入力例は小課題 2, 4, 5, 6, 7, 8 の制約を満たす．
入力例 3

出力例 35 5 20

1 2

12 3

32 4

3

3 5

4

4 501100
1 5
この入力例は小課題 3, 4, 5, 6, 7, 8 の制約を満たす．

ボードゲーム– 4 / 5

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 2 – Board Game
入力例 4

出力例 48 7 541 325 734 602 6102 317 8171 52410011010
4 6 4 7 1
この入力例は小課題 4, 6, 7, 8 の制約を満たす．
入力例 5

出力例 512 13 301 212 343 454 565 676 787 888 949 101

1 10132 997 1211 12110000011101
1 9 11
この入力例は小課題 4, 6, 7, 8 の制約を満たす．

ボードゲーム– 5 / 5