Problem Description

You have $n+1$ sticks, initially each of the sticks numbered from $1$ to $n$ has 3 disks on it, with colors not exceeding $n$ different colors.

In each operation, you can choose a pair $(a_i, b_i)$, indicating that the top disk of stick $a_i$ is moved to the top of stick $b_i$ (stick $a_i$ must have at least one disk, and stick $b_i$ can have at most 2 disks).

You need to construct a valid sequence of operations such that after all operations, each stick has disks of the same color and the $(n+1)$-th stick is empty.

Input Format

The first line contains an integer $n\ (1 \leq n \leq 1000)$, representing the number of sticks.

The next 3 lines, each containing $n$ integers $c_{i,j}\ (1 \leq c_{i,j} \leq n)$, describe the colors of the disks on the $j$-th stick from top to bottom.

Output Format

The first line contains an integer $k\ (1 \leq k \leq 6n)$, representing the number of operations.

The following $k$ lines, each containing a pair $(a_i, b_i)$, describe the pairs of sticks involved in the operations.

Sample Input and Output

Sample Input #1

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

Sample Output #1

8
3 5
3 5
2 3
2 5
2 3
5 2
5 2
5 2

Sample Input #2

2
1 2
1 2
1 2

Sample Output #2

0

见题面 Input 部分

见题面 Output 部分