Friends and Enemies
On the island of Gentu, there are n crocodiles. Each crocodile has exactly one friend and one enemy among the other crocodiles. The relationships are mutual: if crocodile A is a friend of crocodile B, then B is also a friend of A; similarly, if A is an enemy of B, then B is an enemy of A. No crocodile is both a friend and an enemy of another, and no crocodile can be its own friend or enemy.
The crocodiles are quite emotional. When two enemies meet, they fiercely pound the ground with their tails, leading to a Crocodile Battle. When two friends meet, they perform the destructive Crocodile Friendship Dance.
Recently, these dances and battles have awakened the volcano beneath the island, causing it to split into two parts. Although the volcano has calmed, the crocodiles fear that further dances and battles might trigger another eruption, flooding both halves of the island with lava.
The crocodiles now wish to settle on the two halves of the island such that each half contains a neutral set of crocodiles—meaning no two crocodiles in the same set are friends or enemies. By doing so, they hope to prevent any dances or battles, thus avoiding another volcanic eruption.
The crocodiles of Gentu Island are wise but impractical. They know that, given their relationships, it is always possible to divide themselves into two neutral sets, but they don't know how to achieve this division.
Help them! Find a way to divide the crocodiles into two sets so that within each set, no crocodile has a friend or enemy.
Input
The first line of the input contains a natural number n—the number of crocodiles (4 ≤ n ≤ 100). The following n lines describe the crocodiles. The first line contains two numbers f_1 and e_1, separated by a space—the friend and enemy of the first crocodile. The second line contains f_2 and e_2—the friend and enemy of the second crocodile, and so on. The last line contains f_n and e_n—the friend and enemy of the n-th crocodile. The crocodiles are numbered from 1 to n in the order they appear in the input.
All numbers f_k and e_k are integers within the range from 1 to n, inclusive. The relationships of friendship and enmity are symmetrical. The friend and enemy of each crocodile are distinct. No crocodile is its own friend or enemy.
Output
In the first line of the output, print n numbers separated by spaces. Each number should be either 1 or 2. If the i-th and j-th numbers are the same, it means crocodiles i and j are on the same half of the island. If they are different, it means crocodiles i and j are on different halves.
If there are multiple correct solutions, any of them can be provided.