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. Input The input file contains several data sets, each of them as described below. Consecutive data sets are separated by a single blank line. The first line of the data set 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. Output For each data set in the input the output must follow the description below. The outputs of two consecutive data sets will be separated by a blank line. The output 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. Sample Input 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
2/2 5-6 7-8 Sample Output 14 22 31 43 51 62 71 82