Three planets \(X\), \(Y\) and \(Z\) within the Alpha planetary system are inhabited with an advanced civilization. The spaceports of these planets are connected by interplanetary space shuttles. The flight scheduler should decide between \(1\), \(2\) and \(3\) return flights for every existing space shuttle connection. Since the residents of Alpha are strong opponents of the symmetry, there is a strict rule that any two of the spaceports connected by a shuttle must have a different number of flights.
For every pair of connected spaceports, your goal is to propose a number \(1\), \(2\) or \(3\) for each shuttle flight, so that for every two connected spaceports the overall number of flights differs.
You may assume that:
1) Every planet has at least one spaceport
2) There exist only shuttle flights between spaceports of different planets
3) For every two spaceports there is a series of shuttle flights enabling traveling between them
4) Spaceports are not connected by more than one shuttle
Output
The same representation of shuttle flights in separate rows as in the input, but also containing a third number from the set \(\{1, 2, 3\}\) standing for the number of shuttle flights between these spaceports.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
15
XXXXYYYZZZ
0 4
0 5
0 6
4 1
4 8
1 7
1 9
7 2
7 5
5 3
6 2
6 9
8 2
8 3
9 3
|
0 4 2
0 5 2
0 6 2
4 1 1
4 8 1
1 7 2
1 9 3
7 2 2
7 5 1
5 3 1
6 2 1
6 9 1
8 2 3
8 3 1
9 3 1
|