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 them it is impossible to have both chains. 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 Specification

The first line of input contains two integers, ~N~ and ~E~ ~(1 \le N, E \le 100\,000)~, the number of cities and the 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 cities.

Output Specification

If there is no way to fairly assign the roads, the first and only line of output 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 one.

Subtasks

Tests worth ~60\%~ of the points have ~N \le 1\,000, E \le 5\,000~.

Sample Input 1

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

Sample Output 1

1
2
1
2
2
1

Sample Input 2

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

Sample Output 2

0

Sample Input 3

77777 4
1 2
1 3
1 4
1 5

Sample Output 3

1
2
2
2