Madoka and Homura are two mahou shoujos (magical girls) who know a lot about magician tricks. Last time, Madoka sucessfully performed shuffles perfectly and challenged Homura for a game.

This time, Homura brought $2N$ cards and challenged Madoka for another game. The cards are numbered from $1$ to $N$ and each number appears exactly $2$ times, that is the set of card is $[1, 1, 2, 2, ..., N, N]$.

As a good magical girl, Homura can sort a deck of cards in any desirable way. To challenge Madoka, Homura prepared $N + 1$ empty stacks, where each of them can hold at most $2$ cards. She then shuffled and put all $2N$ cards in the first $N$ card stacks, where the top card of the $i$-th stack is $A_i$ and the bottom card of the $i$-th stack is $B_i$ $(1 \le i \le N)$. Madoka's task is to sort the cards such that each card stack is either empty or contains $2$ cards with the same number. For each operation, Madoka can take the topmost card of a stack and put it at the top of another stack that contains less than $2$ cards. To make the challenge even harder, Homura wants Madoka to sort the cards using the least amount of operations.

Since Madoka is also a good magical girl, she immediately solved the challenge. To check the correctness of her answer and check whether Homura cheated, they asked you to tell them one of the ways that can sort the cards with the least amount of operations. Since you are not mahou shoujo, they would still be happy if you can tell them the least amount of operations needed. It can be shown that there is always a way to sort the cards using finite amount of operations.

Input

The first line of input contains one integer, $N$.
The second line of input contains $N$ integers, where the $i$-th integer is $A_i$.
The third line of input contains $N$ integers, where the $i$-th integer is $B_i$.

Output

The first line of output contains one integer, $M$, the least amount of operations to sort the cards.
The next $M$ lines of output contains two integers, $P_i$ and $Q_i$, describing that for the $i$-th operation, move the topmost card of the $P_i$-th stack to the $Q_i$-th stack. $(1 \le P_i, Q_i \le N + 1, P_i \ne Q_i)$

Scoring

For each test case:

• You score 0% if $M$ is wrong; otherwise
• You score 50% if $M$ is correct but the list of operations is invalid (you can omit outputting the list of operations); otherwise
• You score 100% if $M$ is correct and the list of operations is valid.

Constraints

For all cases, $1 \le N \le 10^5, 1 \le A_i, B_i \le N$
It is guaranteed that each number from $1$ to $N$ apprears exactly $2$ times as $A_i$ or $B_i$.
Subtask 1 (3%): $N = 1$
Subtask 2 (7%): $N = 2$
Subtask 3 (20%): $1 \le N \le 5$
Subtask 4 (20%): $A_i \ne A_j$ for all $i < j$
Subtask 5 (25%): $2 \le N, A_1 = A_2 = 1, A_i \ne A_j$ for all $1 < i < j \le N$
Subtask 6 (25%): No additional constraints