Uniform Color Sorting

You are given n+1 rods. Initially, each of rods 1 through n contains exactly 3 disks, and each disk has a color represented by an integer between 1 and n. The (n+1)-th rod is empty.

You are allowed to perform the following operation: choose a pair of distinct rods (a, b) such that rod a is non‐empty and rod b contains at most 2 disks, then remove the top disk from rod a and place it on top of rod b. Note that there is no restriction on the color when placing a disk.

Your task is to devise a sequence of moves so that when the operations finish, every rod among rods 1 through n is homogeneous (i.e. all disks in that rod have the same color) and the (n+1)-th rod is empty.

All formulas in this problem are shown in LaTeX. For example, the number of rods is given by $n+1$ and a move is represented as $(a_i,b_i)$ meaning that the top disk from rod $a_i$ is moved onto rod $b_i$.

inputFormat

The input begins with a single integer n ($1 \le n \le 8$) on a line by itself. Then follow n lines, each describing the initial configuration of rods 1 through n. Each of these lines contains exactly 3 integers. The three integers represent the colors of the disks on that rod from bottom to top. All disk colors are integers between 1 and n.

outputFormat

First, output an integer m representing the number of moves performed. Then output m lines, each containing two integers a and b (1-indexed) representing that the top disk from rod a is moved to rod b.

The sequence of moves must be valid under the following rules:

• You may only move a disk from a rod that is non-empty.
• You may only move a disk to a rod that currently contains at most 2 disks (since a rod can hold at most 3 disks).

Finally, after performing all moves, for every rod 1 through n, all disks on that rod must have the same color, and rod n+1 must be empty.

sample

1
1 1 1

0