VivoParc Animal Assignment

VivoParc is a zoological park in Valencia. It recently opened a new area, a large flat savanna grassland divided into several enclosures.

Each new enclosure has to hold one animal of one of four species: lions, leopards, tigers, and panthers. These animals are very territorial, so no animal may see another animal of its own species from its enclosure. The park manager sent the visibility data between the enclosures, so assign one species to every enclosure while respecting that data. When the assignment is finished, no enclosure may be left without a species.

The first line contains the number of enclosures $N$. ($1 \le N \le 100$)

Every line from the second one to the end of the file holds one 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. The manager is not a very well organized person, so the same restriction may appear several times, sometimes with the two numbers swapped.

At least one assignment satisfying every restriction exists.

Print one line per enclosure with the enclosure number and the species assigned to it, separated by a space. Species 1 is the lion, 2 the leopard, 3 the tiger, and 4 the panther. Enclosure numbers appear in increasing order from 1 to $N$.

Several assignments can satisfy the restrictions. So that the answer is unique, print the assignment whose species sequence $(c_1, c_2, \dots, c_N)$, read from enclosure 1 to enclosure $N$, is lexicographically smallest. That is, make $c_1$ as small as possible, then keep it fixed and make $c_2$ as small as possible, and continue the same way to the last enclosure.