121. Bridges painting

time limit per test: 0.25 sec.
memory limit per test: 4096 KB

New Berland consists of N (1£ N£ 100) islands, some of them are connected by bridges. There can be no more than one bridge between any pair of islands. Mr. President issued a law to paint all bridges. A bridge can be painted white or black. Any island must have at least one white bridge and at least one black (of course if an island has more than one bridge).

Input

There is N on the fisrt line of input. Next N lines contain a list of islands connected with given island. Every list is finished by 0.

Output

If needed painting exists then write N lines. Write “1” and “2” in each line. Write “1” if bridge is painted white and “2” in other case. Write 0 at the end of any list. If needed painting does not exist then write “No solution”.

Sample Input

6
2 3 0
1 3 0
1 2 5 0
5 0
4 6 3 0
5 0

Sample Output

1 2 0
1 2 0
2 2 1 0
2 0
2 2 1 0
2 0