프로그램 명: coci_res(special judge)
제한시간: 1 초
//sp 가 아직
크로아티아에는 E개의 양방향 도로로 연결된 N개의 도시가 있다. 두개의 큰 음식 업체는 최근 시장공유에 대한 동의했다. 각 도로의 가운데에 정확히 한개의 업체만 레스토랑을 지을 수 있는 권한이 주어진다. 시장을 공정하게 공유하기 위하여, 각 도시는 반드시 도시를 연결하는 도로위에 각 업체들로부터의 레스토랑을 적어도 한개는 가지고 있어야한다. 그러나, 도로가 하나밖에 없거나 도로가 전혀 없는 도시는 두업체의 레스토랑 모두를 가지고 있는건 불가능하다. 이러한 도시는 한 업체만 방문하거나 멀리까지 나가야한다.
각 도로마다의 요구사항에 적합한 업체를 정하는 프로그램을 작성해라.
입력
첫줄은 도시의 개수 N과 도로의 개수 E(1 ≤ N, E ≤ 100 000)인 두개의 정수를 입력합니다. E번째 줄은 각 줄마다 두개의 정수를 입력합니다. 각 라인은 한개의 도로를 나타냅니다. 정수 Ai와 Bi (1 ≤ Ai, Bi ≤ N; Ai ≠ Bi)는 한 도로에 연결된 도시Ai와 Bi를 나타냅니다.
서로 연결된 도시에는 두개 또는 여러개의 도로가 연결될 수 없습니다.
출력
만약 도로를 공정하게 배분할 수 없다면 "0"을 출력합니다. 반면 각 도로를 나타내는 E개의 줄에는 첫번째 업체가 레스토랑을 지을 권한이 있다면 "1"을 출력하고 두번째 업체가 레스토랑을 지을 권한이 있다면 "2"를 출력합니다.
참고 : 답이 하나가 아닌 경우 답 중 하나만 입력하세요.
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.
입출력 예
입력
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
출처: coci
번역: iam6ear
[질/답]
[제출 현황]
[푼 후(0)]