問題文

$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$を満たすように出力してください。
最後に改行してください。

サンプル

3 6 4
1 3
1 2
2 3
? ?
2 3
1 3
1 2 3

1 3

4 3 3
1 2
3 4
? ?
2 3 4 1

2 4

5 7 1
? ?
3 5
2 4
1 3
2 3
1 4
4 5
5 1 4 3 2

2 5