21908번 - Disk Sort 스페셜 저지다국어

문제

You are given $n + 1$ rods and 3ドルn$ disks. Initially, each of the first $n$ rods contains exactly 3ドル$ disks. Each of the disks has one of $n$ colors (identified by numbers from 1ドル$ to $n$). Moreover, there are exactly 3ドル$ disks of each of the $n$ colors. The $n + 1$-th rod is empty.

At each step we can select two rods $a$ and $b$ ($a \ne b$) such that $a$ has at least 1ドル$ disk and $b$ has at most 2ドル$ disks, and move the topmost disk from rod $a$ to the top of rod $b$. Note that no rod is allowed to contain more than 3ドル$ disks at any time.

Your goal is to sort the disks. More specifically, you have to do a number of operations (potentially 0ドル$), so that, at the end, each of the first $n$ rods contains exactly 3ドル$ disks of the same color, and the $n + 1$-th rod is empty.

Find out a solution to sort the disks in at most 6ドルn$ operations. It can be proven that, under this condition, a solution always exists. If there are multiple solutions, any one is accepted.

입력

The first line of the input contains a positive integer $n$ (1ドル \le n \le 1,000円$). The next 3ドル$ lines of the input contain $n$ positive integers $c_{i,j}$ each (1ドル \le i \le 3,ドル 1ドル \le j \le n,ドル 1ドル \le c_{i,j} \le n$), the color each of the disks initially placed on the rods. The first of the 3ドル$ lines indicates the upper row, the second line indicates the middle row, and the third line indicates the lower row.

출력

The first line of the output must contain a non-negative integer $k$ (0ドル \le k \le 6n$), the number of operations. Each of the following $k$ lines should contain two distinct numbers $a_i,ドル $b_i$ (1ドル \le a_i, b_i \le n + 1,ドル for all 1ドル \le i \le k$), representing the $i$-th operation (as described in the statement).

제한

힌트