No.429 CupShuffle

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 150
作問者 : startcppstartcpp / テスター : りあん🐺☔️⛄️りあん🐺☔️⛄️

3 ProblemId : 926 / 出題時の順位表

問題文

$N$個のコップ(コップ$1$~コップ$N$)について交換の仕方・最終配置が与えられます。
$X$回目に交換した$2$個のコップの位置を当ててください。
設定は以下の通りです。
・最初、位置$i$にはコップ$i$があった。
・$k$($1 \le k \le K$, $k \neq X$)回目の交換では、位置$A_k$, $B_k$にあるコップを交換した。
・最終的に、位置$i$にはコップ$C_i$があった。

入力

$N\ K\ X$
$A_1\ B_1$
$A_2\ B_2$
$\dots$
$A_K\ B_K$
$C_1\ C_2\ \dots\ C_N$

$2 \le N \le 100000$
$1 \le K \le 100000$
$1 \le X \le K$
$i \neq X$のとき、$1 \le A_i \lt B_i \le N$
$i = X$のとき、$A_i$ = ?, $B_i$ = ?
$1 \le C_i \le N$
$C_i$は相異なる
答えは存在する

ヒント

case$1$~case$10$では、$N \le 100$, $K \le 1000$を満たす。
答えは一意に定まる。

出力

昇順に出力してください。
すなわち、$A_X \lt B_X$を満たすように出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3 6 4
1 3
1 2
2 3
? ?
2 3
1 3
1 2 3
出力
1 3

4回目の交換で、位置1, 3にあるコップを交換した場合、コップの配置は次のように遷移します。
123
321
231
213
312
321
123

サンプル2
入力
4 3 3
1 2
3 4
? ?
2 3 4 1
出力
2 4

サンプル3
入力
5 7 1
? ?
3 5
2 4
1 3
2 3
1 4
4 5
5 1 4 3 2
出力
2 5

提出ページヘ