P10739 [SEERC 2020] Disk Sort

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.

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$.

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.

Translated by ChatGPT 5