問題文

あみだくじが大好きなゆきこちゃんは今年も「あみだアドベントカレンダー」用にあみだくじを作ります。
ゆきこちゃんはまず「あみだくじの出発点と到着点の対応」を決めてからあみだくじを作り始めました。
最初は順調だったゆきこちゃんでしたが、他のアドベントカレンダーに気を取られ気づいたら担当日の前日！手元にあるのは完成途中のあみだくじ！
そこであなたはゆきこちゃんに代わってあみだくじを完成させるプログラムを作ってください。

完成途中のあみだくじは $N$ 本の縦線と、それに垂直な $K$ 本の横棒で構成されています。
$K$ 本の横棒はいずれも異なる高さにあり、上から $k$ 番目の横棒は、左から $X_k$ 番目の縦線と 左から $Y_k$ 番目の縦線を繋いでいます。

ゆきこちゃんが最初に決めた「あみだくじの出発点と到着点の対応」は $1\sim N$ の順列 $A_i(1\le i\le N)$ で表現されます。
これは、左から $i$ 本目の縦棒を出発すると、左から $A_i$ 本目の縦棒に到着することを表します。

入力

$N$
$K$
$X_1$ $Y_1$
$⋮$
$X_K$ $Y_K$
$A_1$ $\dots$ $A_N$

1行目に縦棒の数 $N$、2行目に横棒の数 $K$ が与えられます。
以下 $K$ 行に横棒の情報が与えられます。
$3+K$ 行目に、出発点と到着点の対応を表す $A_i(1\le i\le N)$ が空白区切りで与えられます。

入力は全て整数で、以下の制約を満たします。

• $2\le N\le 100$
• $0\le K\le 6000$
• $1\le X_i<Y_i\le N$
• $X_i+1=Y_i$
• $A_i$ は 列 $1,2,\dots ,N$ を並べ替えたもの

出力

上から $K$ 番目の横棒より下に何本か横棒を付け加えてあみだくじを完成させてください。

この問題はスペシャルジャッジです。
後述の出力形式に沿った解が複数ある場合どれを出力しても構いません。
出力可能な解が少なくとも一つあることが保証されています。

出力形式

付け加える横棒を以下の形式で出力してください。

$L$
$X_{K+1}$ $Y_{K+1}$
$⋮$
$X_{K+L}$ $Y_{K+L}$

出力は全て整数で、以下の制約を満たしてください。

• $L$ 本の横棒を付け加える。
• 完成したあみだくじは $K+L$ 本の横棒で構成されており「あみだくじの出発点と到着点の対応」は $A$ と一致する。
• $K+L$ 本の横棒はいずれも異なる高さにあり、上から $k(1\le k\le K+L)$ 番目の横棒は、左から $X_k$ 番目の縦線と 左から $Y_k$ 番目の縦線を繋いでいるとする。
• $0\le L\le 6000$
• $1\le X_i<Y_i\le N$
• $X_i+1=Y_i$

サンプル

サンプル1

入力サンプルをコピー

入力

5
6
1 2
3 4
2 3
3 4
1 2
4 5
5 1 4 3 2

出力

3
1 2
3 4
2 3

例えば下のように3本付け加えると完成します。

サンプル2

入力サンプルをコピー

入力

6
4
1 2
2 3
5 6
3 4
2 6 3 1 5 4

出力

11
1 2
5 6
3 4
5 6
3 4
2 3
1 2
3 4
2 3
4 5
5 6

例えば下のように11本付け加えると完成します。