問題文

長さ $N$ の整数列 $A=(A_1,\ A_2,\ \dots,\ A_N),\ B=(B_1,\ B_2,\ \dots,\ B_N)$ および $M$ 個の $2$ 頂点の組 $(u_i,\ v_i)\ (1\le i \le M)$ が与えられます。

$N$ 頂点 $\frac{N(N-1)}{2}-M$ 辺の有向グラフ $G$ があります。$2$ 頂点 $x,\ y\ (1\le x < y \le N)$ 間の有向辺については

• ある整数 $i\ (1\le i \le M)$ があって $(x,\ y)=(u_i,\ v_i)$ が成り立つとき

頂点 $x,\ y$ 間に有向辺は存在しない。

• そうでない場合

$A_x < B_y$ のとき頂点 $x$ から頂点 $y$ へ向かう有向辺が、そうでないとき頂点 $y$ から頂点 $x$ へ向かう有向辺が存在する。

が成り立ちます。

以下の条件を満たす単純有向グラフ $G'$ を $1$ つ求めて下さい。この問題の制約の下で条件を満たす $G'$ が $1$ つ以上存在することが証明できます。

• 頂点数は $N$ であり、辺の数は $3 \times 10^5$ 以下
• 「グラフ $G$ において頂点 $x$ から頂点 $y$ へのパスが存在する $\iff$ グラフ $G'$ において頂点 $x$ から頂点 $y$ へのパスが存在する」が成り立つ

入力

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

• $1 \le N \le 5 \times 10^4$
• $0 \le M \le \min(\frac{N(N-1)}{2},10^5)$
• $1 \le A_i,B_i \le 2N$
• $i \neq j$ ならば $A_i \neq A_j,\ B_i \neq B_j$
• $A_i \neq B_j\ (1\le i,\ j \le N)$
• $1 \le u_i < v_i \le N$
• $i \neq j$ ならば $(u_i,\ v_i) \neq (u_j,\ v_j)$
• 与えられる入力はすべて整数

出力

$G'$ の辺数を $M'$ 、 $i$ 番目の辺は頂点 $u'_i$ から頂点 $v'_i$ へ向かう辺であるとして、以下の形式で出力してください。

$M'$
$u'_1$ $v'_1$
$u'_2$ $v'_2$
$\vdots$
$u'_{M'}$ $v'_{M'}$

出力は（問題の条件に加えて）以下の条件を満たす必要があります。

• $0 \le M' \le 3 \times 10^5$
• $1 \le u'_i,\ v'_i \le N$
• $i \neq j$ ならば $(u'_i,\ v'_i) \neq (u'_j,\ v'_j)$

条件を満たすグラフが複数存在する場合、いずれを出力してもかまいません。

最後に改行してください。

サンプル

4 1
7 3 1 5
4 2 8 6
1 2

4
1 3
2 3
3 4
4 1

4 6
5 1 3 7
8 2 6 4
1 2
1 3
3 4
2 3
1 4
2 4

0