The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Jail

刑務所 (Jail)IOI 刑務所は，JOI 国で最も厳重に管理された刑務所として知られている．この刑務所には N 個の部屋があり，1 から N までの番号が付けられている．また，この刑務所には N − 1 本の通路があり，i 番目(1 ≦ i ≦ N − 1) の通路は部屋 Ai と部屋 Bi を双方向に結んでいる．どの部屋からどの部屋へも，いくつかの通路を通ることで移動することができる．

IOI 刑務所には M 人の受刑者が収容されている．各受刑者には 1 から M までの「称呼番号」が付けられており，称呼番号 j (1 ≦ j ≦ M) の受刑者の寝室は部屋 S j ，作業場所は部屋 T j である．ある受刑者の寝室が別の受刑者の作業場所に割り当てられていることはあるが，同じ部屋が複数の受刑者の寝室に割り当てられたり，同じ部屋が複数の受刑者の作業場所に割り当てられたりすることはない．
ある日の朝，M 人の受刑者全員を寝室から作業場所まで移動させることになった．IOI 刑務所の所長である APIO 氏は，以下の命令を繰り返すことで受刑者を移動させる．
命令 受刑者を 1 人選び，その受刑者を（現在いる部屋から）通路で直接結ばれている部屋に移動させる．
ただし，刑務所内での私語を防ぐため，移動先の部屋には他の受刑者がいてはならない．
刑務作業を早く始めるため，APIO 氏は，すべての受刑者が同じ部屋を二度通らずに最短経路で移動を完了させることが可能かどうかを判定したい．

IOI 刑務所の部屋と通路の情報，受刑者の情報が与えられるので，すべての受刑者が最短経路で移動を完了させることが可能かどうかを判定するプログラムを作成せよ．

刑務所– 1 / 6

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Jail入力
1 つのテストケースは Q 個のシナリオからなり，シナリオには 1 から Q までの番号が付けられている．
各シナリオに対して，以下の値が定められている．ただし，以下に記された値の範囲については，制約の項を参照せよ．

• IOI 刑務所にある部屋の数 N ．
• IOI 刑務所の通路の情報 (A1 , B1 ), (A2 , B2 ), · · · , (AN−1 , BN−1 )．
• IOI 刑務所に収容されている受刑者の数 M ．
• 各受刑者の寝室と作業場所の部屋番号 (S 1 , T 1 ), (S 2 , T 2 ), · · · , (S M , T M )．
ここで，入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

Q(シナリオ 1 に対する入力)(シナリオ 2 に対する入力)..
.
(シナリオ Q に対する入力)
また，それぞれのシナリオに対する入力は，以下の形式で与えられる．詳しくは入出力例の項を参照せよ．

NA1 B1A2 B2..
.
AN−1 BN−1M
S 1 T1S 2 T2..
.
S M TM

刑務所– 2 / 6

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Jail

出力
標準出力に Q 行で出力せよ．k 行目 (1 ≦ k ≦ Q) には，以下を出力せよ．

• シナリオ k について，すべての受刑者を最短経路で移動させることが可能なとき Yes．
• シナリオ k について，すべての受刑者を最短経路で移動させることが不可能なとき No．

制約• 1 ≦ Q ≦ 1 000．
• 2 ≦ N ≦ 120 000．
• 1 ≦ Ai < Bi ≦ N (1 ≦ i ≦ N − 1)．
• 2 ≦ M ≦ N．
• 1 ≦ S j ≦ N (1 ≦ j ≦ M)．
• 1 ≦ T j ≦ N (1 ≦ j ≦ M)．
• S 1 , S 2 , · · · , S M は相異なる．
• T 1 , T 2 , · · · , T M は相異なる．
• S j , T j (1 ≦ j ≦ M)．
• どの部屋からどの部屋へも，いくつかの通路を通ることで移動することができる．
• Q 個のシナリオにおける N の値の合計は 120 000 以下である．

小課題
1. (5 点) Ai = i， Bi = i + 1 (1 ≦ i ≦ N − 1)．
2. (5 点) Q ≦ 20，N ≦ 250， M = 2．
3. (16 点) Q ≦ 20，N ≦ 250， M ≦ 6．
4. (28 点) Q ≦ 20，N ≦ 250， M ≦ 100．
5. (12 点) Q ≦ 20， M ≦ 500．
6. (11 点) どの部屋からどの部屋へも，高々 20 本の通路を使って移動することができる．
7. (23 点) 追加の制約はない．

刑務所– 3 / 6

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Jail

入出力例
入力例 1

出力例 11Yes81 22 33 44 55 66 77 823 44 8
この入力例では，次のような手順で命令を出すことにより，すべての受刑者を最短経路で移動させることができる．

1. 称呼番号 2 の受刑者を，部屋 4 から部屋 5 に移動させる．
2. 称呼番号 1 の受刑者を，部屋 3 から部屋 4 に移動させる．
3. 称呼番号 2 の受刑者を，部屋 5 から部屋 6 に移動させる．
4. 称呼番号 2 の受刑者を，部屋 6 から部屋 7 に移動させる．
5. 称呼番号 2 の受刑者を，部屋 7 から部屋 8 に移動させる．
したがって，Yes を出力する．なお，この入力例における刑務所の構造は以下の図のようになっている．
この入力例はすべての小課題の制約を満たす．

13254

刑務所– 4 / 6768

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Jail
入力例 2

出力例 22Yes7No1 22 33 44 53 66 724 15 741 21 31 432 33 44 2
この入力例は Q = 2 個のシナリオからなる．シナリオ 1 では，次のような手順で命令を出すことにより，すべての受刑者を最短経路で移動させることができる．

1. 称呼番号 1 の受刑者を，部屋 4 から部屋 3 に移動させる．
2. 称呼番号 1 の受刑者を，部屋 3 から部屋 2 に移動させる．
3. 称呼番号 2 の受刑者を，部屋 5 から部屋 4 に移動させる．
4. 称呼番号 2 の受刑者を，部屋 4 から部屋 3 に移動させる．
5. 称呼番号 2 の受刑者を，部屋 3 から部屋 6 に移動させる．
6. 称呼番号 1 の受刑者を，部屋 2 から部屋 1 に移動させる．
7. 称呼番号 2 の受刑者を，部屋 6 から部屋 7 に移動させる．
一方，シナリオ 2 では，すべての受刑者を最短経路で移動させることはできない．したがって，1 行目には Yes，2 行目には No を出力する．
この入力例は小課題 3, 4, 5, 6, 7 の制約を満たす．

刑務所– 5 / 6

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Jail入力例 3

出力例 33Yes

3No

1 2Yes

2 322 13 27
1 22 33 4
4 55 66 73
1 34 2
2 58
1 22 33 44 55 6
6 77 84
1 52 63 74 8
この入力例は小課題 1, 3, 4, 5, 6, 7 の制約を満たす．

刑務所– 6 / 6