# 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.

Sample Input 1 | Sample Output 1 |
---|---|

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

Sample Input 2 | Sample Output 2 |
---|---|

7 7 1 2 2 3 3 1 4 5 5 6 6 7 7 4 |
0 |

Sample Input 3 | Sample Output 3 |
---|---|

77777 4 1 2 1 3 1 4 1 5 |
1 2 2 2 |