Greek Matchmaker

During the Greco-Persian Wars, many Greek city-states configured their entire society to maximize military proficiency at all costs. Private interests and personal happiness were often subordinated to the good of the public, and the ancient Greek legislators considered that even marriage is a matter of public interest. For example, in Sparta, the laws of Lycurgus of Sparta required that criminal proceedings be taken against those who married too late, as well as against confirmed bachelors. Plutarch, the famous Greek biographer and essayist, reports the peculiar customs associated with marriages and weddings in this ancient period.

In the city of Laodicea ad Sipylum, couples were formed once a year when young men were home from the wars, through an intricate matchmaking dancing ceremony:

1. N girls and N boys, suitable for marriage, were chosen.
2. The high priestess of the Temple of Aphrodite, after praying for visions, would choose a number M, called shuffle rounds.
3. Once M was revealed, the N girls were lined up into a queue according to the alphabetical order of their names. Then the high priestess of the Temple of Aphrodite would arrange the N boys into a parallel queue, in an order she saw fit, in accordance with her visions and divine inspirations.
4. After the queues were formed, the dance ceremony began, everybody dancing in place to the rhythm.
5. Periodically, when he felt inspired, the priest of the Temple of Ares would hit the rhoptron (a special buzzing drum used in Ancient Greece) or blow the salpinx (a trumpet-like instrument of the ancient Greeks). Whenever the rhoptron was hit, the first girl at the top of the girls' queue would go dancing to the back of the queue, and similarly, when the salpinx was blown, the boy from the top of the boys' queue went to the back. There was no specific order or even a fixed distribution on how the sound instruments were played, the priest of the Temple of Ares always acted in the moment, randomly, on how he felt inspired.
6. After the instruments were played M times, i.e., M young people shuffled cyclically to the back of their respective queues, the music was paused for a moment: the girl and the boy on the top of the queues were declared a couple, and they were removed from the queues to go and start preparing for their wedding.
7. Then, the music resumed, and the next couple was determined after M new shuffles.
8. Steps 5–7 were repeated until just one boy and one girl remained in the queues: the final couple.

Let's see an example for N = 3 and M = 3. Starting from the initial queues from the first two columns, if, for example, first the rhoptron (R) is hit, then the salpinx (S) is sounded twice, the first couple would be (Eileithyia, Philpoemon):

In the second matchmaking round, if the rhoptron is played first, then the salpinx, then the rhoptron again, the second couple would be (Rhene, Haemon):

The two last persons (Alcippe, Epitrophos) would form the final couple.

One year, while the high priestess of the Temple of Aphrodite was praying for visions and divine inspirations regarding the suitable shuffle round value M and for guidance on how to arrange the boys initially in the queue, Eros, the Greek god of love, visited her. Being after a long night of partying on Mount Olympus, Eros could not be bothered to do the math and reveal the sacred order on how boys should be queued and what is the required divine shuffle number that form the perfect couples. Instead, Eros only provided the high priestess with the perfect couples' list, containing N pairs of names, each pair describing a girl and her match.

It is your task to help the high priestess of the Temple of Aphrodite and do the job of the Olympian Greek Gods! Decide how the boys should be queued and what the smallest positive integer for shuffle rounds is such that the ceremony will lead to the formation of the couples as described by Eros' list.

Input Specification

The first line of the input contains the number N (3 ≤ N ≤ 50 000), the number of boys, girls, and couples to be. The following N lines describe the perfect couples as intended by the Greek Gods, containing two names per line, that of a girl followed by that of a boy. The names on a line are separated by a space character.

Every girl and every boy has a different name (unique identifier), containing only alphanumeric characters, and every name can be found only once in the input (there is no person belonging to multiple couples).

Output Specification

Output the name of the boys in the order they should be queued, one name per line. In the last line, output the smallest positive integer for shuffle rounds M modulo 1 000 000 007 (10⁹ + 7) such that the ceremony leads to the formation of the couples as specified in the input. The ceremony requires that at least 2 dance rounds to be performed (M ≥ 2).

Sample Input

1. 3
2. Rhene Haemon
3. Alcippe Philpoemon
4. Eileithyia Epitrophos

download as text file

Output for Sample Input

1. Haemon
2. Epitrophos
3. Philpoemon
4. 5

download as text file