Problem Description

You have $n + 1$ rods. Initially, each rod from $1$ to $n$ has $3$ disks on it, and the number of possible colors does not exceed $n$.

In each operation, you may choose a pair $(a_i, b_i)$, meaning moving the top disk of rod $a_i$ onto the top of rod $b_i$ (rod $a_i$ must have at least $1$ disk, and rod $b_i$ can have at most $2$ disks).

You need to construct a valid sequence of operations such that after all operations, the colors of the disks on each rod are all the same, and rod $n + 1$ is empty.

Input Format

The first line contains an integer $n\ (1 \leq n \leq 1000)$, meaning there are $n$ rods.

The next $3$ lines each contain $n$ integers $c_{i,j}\ (1 \leq c_{i,j} \leq n)$, where $c_{i,j}$ is the color of the $i$-th disk from top to bottom on rod $j$.

Output Format

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

Then follow $k$ lines, each containing a pair $(a_i, b_i)$, indicating the move operation.

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

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

2
1 2
1 2
1 2

0

Hint

Translated by ChatGPT 5