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

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\)-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.

Scoring: This task has test cases grouped into test runs. In order to score points for a test run, all test cases in the run must be solved correctly. Test runs worth \(60\%\) of points have \(N \le 1000\), \(E \le 5000\).

riseoj 작성

출처 COCI 2009/2010 Contest 7