The warehouse stores containers with N different types of goods. All containers are arranged in N stacks. Each stack can contain containers of any kind of goods (the stack can be initially empty).
The forklift can take the top container from any stack and place it on top of any stack. It is necessary to arrange all containers with the goods of the first type in the first pile, the second type – to the second pile, etc.
The program should display a sequence of actions of the forklift or a message that the task has no solution.
Input
The first line of the input contains one natural number N, not exceeding 500. The next N lines describe stacks of containers: first, the number k
i – the number of containers in the stack, followed by k
i numbers – types of goods in containers in this stack, from bottom to top. Each stack initially has a maximum of 500 containers (this limit may be violated during container transfer).
Imprint
The program should display a description of the actions of the forklift: for each action, print two numbers – from which pile to take the container and in which pile to put it. (Note that you don't need to minimize the number of forklift operations.) If the problem has no solution, you should print a single number 0. If the containers are initially correctly stacked, then you don't need to output anything.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
3
4 1 2 3 2
0
0 |
1 2
1 3
1 2
| Initially, the first stack contains four – below the container with the goods of the first type, above it – with goods of the second type, above it the third, and on top another container with goods of the second type. The second and third piles – empty. |