Problem J
Restoran

In Croatia there are $N$ cities connected by $E$ two-way roads. Two large food chains have recently reached an agreement on market sharing. In the middle of each road, exactly one chain will be given rights to build a restaurant.

To ensure the market is shared fairly, each city must have at least one restaurant from each chain on the roads connected to that city. However, there are cities with only one road, or no roads at all, and for those cities the above requirement does not apply. Such cities are doomed to visit one chain, or travel a bit further.

Write a program that will determine for each road the chain that should build there so that these requirements are met.

Input

The first line of input contains two integers $N$ and $E$ ($1 \le N, E \le 100\, 000$), number of cities and number of roads.

The next $E$ lines contain two integers each. Each line describes one road. Integers $A_ i$ and $B_ i$ ($1 \le A_ i , B_ i \le N$; $A_ i \ne B_ i$) denote a road connecting cities $A i$ and $B_ i$.

There will never be two or more roads connecting the same pair of cities.

Output

If there is no way to fairly assign the roads, the first and only line of input should contain “0”.

Otherwise output exactly $E$ lines, one for each road, in the same order as they were given in the input. The $i^\text {th}$ line should contain “1” if the first chain has the right to build on this road, or “2” if the second one does.

Note: if the solution is not unique, you may output any valid solution.

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

1
2
1
2
2
1

7 7
1 2
2 3
3 1
4 5
5 6
6 7
7 4

0

77777 4
1 2
1 3
1 4
1 5

1
2
2
2