ダンジョンのデッドロック 4
(paizaランク B 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
(電脳言語のオルダーソンループで出題された問題のヒント問題です。8 言語での解答コードと解説が用意されています。)
あなたは RPG のダンジョンの設計をしています。
そのダンジョンには N 個の部屋が用意されており、それぞれの部屋は 1, 2, ..., N で表されます。このダンジョンでは 1 部屋に 1 プレイヤーしか滞在できません。
また、プレイヤーは M 人いて、現在 i (1 ≦ i ≦ M) 番目のプレイヤーは部屋 S_i (1 ≦ S_i ≦ N) に滞在しています。
ダンジョンをクリアするには、プレイヤーはそれぞれ、部屋を移動する必要があります。
M 人のプレイヤーはそれぞれ、移動先の部屋の候補を検討しています。具体的には、i (1 ≦ i ≦ M) 番目のプレイヤーは移動先の部屋の候補として部屋 T_i (1 ≦ T_i ≦ N) を検討しています。ここで、T_i は相異なる整数です。すなわち、異なる 2 人のプレイヤーの移動先の部屋の候補が同じ部屋になることはありません。
ここで、まず 1 番目のプレイヤーが部屋 T_1 に移動することにしました。
しかし、プレイヤーが部屋を移動しようと思っても、その部屋はまだ別のプレイヤーが滞在しているかもしれません。その場合はプレイヤーは部屋を移動することができません。移動先にいるプレイヤーが先に移動するのを待つ必要があります。同じタイミングで同時に移動をおこなうことはできません。
そこで、移動しようとしているプレイヤーの、移動先の候補の部屋にプレイヤーがいる場合は、そのプレイヤーが自身の移動先の候補の部屋に移動した後に移動をすることにしました。しかし、移動する予定の全てのプレイヤーの移動先の部屋にプレイヤーがいて、順番に移動が行えない場合があります。このような状態のことを、デッドロックと呼ぶことにします。
あなたの仕事は、デッドロックが起きるか起きないかを判定し、デッドロックが起きない場合は、1 番目のプレイヤーの移動を完了させるために移動をすることになるプレイヤーの番号を順番に全て求めることです。
ただし、滞在している部屋と移動先の部屋が同じ場合、つまり S_i = T_i (1 ≦ i ≦ M) の場合、そのプレイヤーは移動ができることとします。
- 入力される値
-
N M
S_1 T_1
S_2 T_2
...
S_M T_M
・1 行目には、ダンジョンの部屋の数 N ,プレイヤー数 M がこの順で半角スペース区切りで与えられます。
・続く M 行のうちの i 行目 (1 ≦ i ≦ M) には、i 人目のプレイヤーの現在滞在している部屋 S_i, 移動先の候補の部屋 T_i がこの順で半角スペース区切りで与えられます。
・入力は合計で M + 1 行となり、 入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
・合計 1 行または 2 行出力してください。末尾に改行を入れ、余計な文字、空行を含んではいけません。
・1 行目に、デッドロックが発生する場合は "Yes" を、発生しない場合は "No" を出力してください。
・デッドロックが発生する場合は、出力は 1 行のみです。
・デッドロックが発生しない場合は、2 行目に、1 番目のプレイヤーの移動を完了させるために移動をすることになるプレイヤーの番号を、移動する順に半角スペース区切りで出力してください。
- 条件
-
全てのテストケースにおいて、以下の条件を満たします。
・1 ≦ N ≦ 100,000
・1 ≦ M ≦ N
・1 ≦ S_i ≦ N (1 ≦ i ≦ M)
・1 ≦ T_i ≦ N (1 ≦ i ≦ M)
・S_i ≠ S_j (1 ≦ i, j ≦ M, i ≠ j)
・T_i ≠ T_j (1 ≦ i, j ≦ M, i ≠ j)
- 入力例1
-
5 4
1 2
2 3
3 4
4 5
- 出力例1
-
No
4 3 2 1
- 入力例2
-
5 4
4 4
2 3
3 2
1 1
- 出力例2
-
No
1
- 入力例3
-
5 4
1 2
2 3
3 4
4 1
- 出力例3
-
Yes
