408340: GYM103102 D Disk Sort

You are given $$$n + 1$$$ rods and $$$3n$$$ 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 \neq 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 $$$6n$$$ 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 \leq n \leq 1\,000$$$). The next $$$3$$$ lines of the input contain $$$n$$$ positive integers $$$c_{i, j}$$$ each ($$$1 \leq i \leq 3$$$, $$$1 \leq j \leq n$$$, $$$1 \leq c_{i, j} \leq 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 \leq k \leq 6n$$$), the number of operations. Each of the following $$$k$$$ lines should contain two distinct numbers $$$a_i, b_i$$$ ($$$1 \leq a_i, b_i \leq n + 1$$$, for all $$$1 \leq i \leq k$$$), representing the $$$i$$$-th operation (as described in the statement).

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