Friends and Enemies#2476

Friends and Enemies

1 second

256 megabytes

Easy

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 crocodile, 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 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 so that each half contains a neutral set of crocodiles—meaning that 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, with their pattern of friendships and enmities, it is always possible to divide themselves into two neutral sets, but they do not 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 \leq n \leq 100$ 4 \leq n \leq 100). The following $n$ lines describe the crocodiles. The first line contains two numbers $f_{1}$ f_1 and $e_{1}$ e_1, separated by a space—the friend and enemy of the first crocodile. The second line contains $f_{2}$ f_2 and $e_{2}$ e_2—the friend and enemy of the second crocodile, and so on. The last line contains $f_{n}$ f_n and $e_{n}$ 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}$ f_k and $e_{k}$ e_k are integers in 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, crocodiles $i$ and $j$ are on the same half of the island. If they are different, crocodiles $i$ and $j$ are on different halves.

If there are multiple correct solutions, you may output any of them.

Examples

Example 1