Problem Statement

You are given integer sequences $A=(A_1,\ A_2,\ \dots,\ A_N),\ B=(B_1,\ B_2,\ \dots,\ B_N)$ of length $N$, and $M$ pairs of $2$ vertices $(u_i,\ v_i)\ (1\le i \le M)$.

There is a directed graph $G$ with $N$ vertices and $\frac{N(N-1)}{2}-M$ edges. Regarding the directed edge between $2$ vertices $x,\ y\ (1\le x < y \le N)$, the following holds:

• If there exists an integer $i\ (1\le i \le M)$ such that $(x,\ y)=(u_i,\ v_i)$:

There is no directed edge between vertices $x,\ y$.

• Otherwise:

If $A_x < B_y$, there is a directed edge from vertex $x$ to vertex $y$; otherwise, there is a directed edge from vertex $y$ to vertex $x$.

Find $1$ simple directed graph $G'$ satisfying the following conditions. It can be proved that at least $1$ such $G'$ exists under the constraints of this problem.

• The number of vertices is $N$, and the number of edges is at most $3 \times 10^5$.
• "There is a path from vertex $x$ to vertex $y$ in graph $G$ $\iff$ there is a path from vertex $x$ to vertex $y$ in graph $G'$" holds.

Input

$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$
• If $i \neq j$, then $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$
• If $i \neq j$, then $(u_i,\ v_i) \neq (u_j,\ v_j)$
• All input values are integers.

Output

Let $M'$ be the number of edges of $G'$, and let the $i$-th edge be directed from vertex $u'_i$ to vertex $v'_i$. Output in the following format.

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

In addition to the conditions of the problem, the output must satisfy the following conditions.

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

If there are multiple graphs satisfying the conditions, you may output any of them.

Print a newline at the end.

Sample

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