시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 21 6 5 31.250%

문제

Vivoparc is a zoological park located in Valencia. It has recently added a new area formed by a big plane savanna grassland divided into several enclosures.

Our purpose is to assign one animal of the 4 different species (lions, leopards, tigers, and panthers) to each of the new VivoParc enclosures. These animals are very territorial therefore we must be sure that no animal can see other animal of its own species from its enclosure. The Vivoparc manager has sent us a file with the visibility from the different enclosures and we have to assign one species to each enclosure. At the end of the process, all the enclosures must have an assigned species.

입력

The first line of the input file contains the number of enclosures (N ≤ 100). Each of the following lines contain a visibility restriction: 1-3 means that animals in enclosure #1 can see animals in enclosure #3 and animals in enclosure #3 can see animals in enclosure #1. Note that the Vivoparc manager is not a very well organized person and therefore, some data appearing in the file may be redundant.

출력

The output file contains one of all the possible species assignation. The file consists of a line per enclosure and each line contains the number of the enclosure followed by the assigned species (1= Lion, 2= Leopard, 3= Tiger, 4= Panther). Enclosures assignation must appear in ascending order.

예제 입력

8
1-2
3-1
4-5
4-8
1-7
1-4
7-1
2-4
1-8
6-7
2-3
1-5
1-6
7-6
7-8
2-5
7-1
3-4
5-6
7-8

예제 출력

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

힌트