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

Author: Michael R. Mirzayanov
Resource: PhTL #1 Training Contests
Date: Fall 2001