문제

In Croatia there are N cities connected by E twoway 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.

입력

The first line of input contains tow integers N and E (1 ≤N, E ≤100 000), number of cities and number of roads. The next E lines contain two integers each. Each line describes one road. Integers Ai and Bi (1 ≤Ai, Bi ≤N; Ai ≠Bi) denote a road connecting cities Ai and Bi There will never be two or more roads connecting the same cities.

출력

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 ith line should contain "1" if the first chain has the right to build onthis road, or "2" if the second one does. Note: if the solution is not unique, you may output any valid one.

예제 입력 1

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

예제 출력 1

1
2
1
2
2
1

예제 입력 2

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

예제 출력 2

0

예제 입력 3

77777 4
1 2
1 3
1 4
1 5

예제 출력 3

1
2
2
2