SEERC 2021

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 (ab) 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 contains a positive integer n (1n1000). The next 3 lines contain n positive integers ci,j each (1i3, 1jn, 1ci,jn), 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 must contain a non-negative integer k (0k6n), the number of operations. Each of the following k lines should contain two distinct numbers ai, bi (1ai, bin + 1, for all 1ik), representing the i-th operation (as described in the statement).

Time limit 1 second
Memory limit 128 MiB
Input example #1
2 3 1 4
2 1 1 4
2 3 3 4
Output example #1
3 5
3 5
2 3
2 5
2 3
5 2
5 2
5 2
Input example #2
1 2
1 2
1 2
Output example #2
Source 2020 SEERC South Eastern European Regional Programming Contest, Vinnica & Bucharest, May 23, Problem D