ダンジョンのデッドロック 3
(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) の場合、そのプレイヤーは移動ができることとします。また、部屋の移動を繰り返すことで 1 番目のプレイヤーが必ず移動できることが保証されます。
- 入力される値
-
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 番目のプレイヤーの部屋の移動を完了させるために移動をすることになるプレイヤーの番号を、移動する順に半角スペース区切りで出力してください。末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
全てのテストケースにおいて、以下の条件を満たします。
・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 番目のプレイヤーが必ず移動できることが保証される
- 入力例1
-
5 4
1 2
2 3
3 4
4 5
- 出力例1
-
4 3 2 1
- 入力例2
-
5 4
4 4
2 3
3 2
1 1
- 出力例2
-
1
