Race Bib Numbers

A nationwide marathon is going to be held. Because the event is very large, the organizers give every participant a T-shirt with bib numbers printed on it, and the participants run while wearing those shirts.

Each T-shirt can be worn either way. It has a bib number printed on both the inside and the outside, so a participant may choose which side faces outward.

However, the number combination on each T-shirt is not guaranteed to be unique. If the participants choose directions carelessly, two participants may show the same bib number.

Write a program that decides, for every T-shirt, which side should face outward so that all visible bib numbers are different.

The first line contains the number of T-shirts N. (1 <= N <= 1,000,000)

Each of the next N lines contains two natural numbers: the bib numbers printed on the inside and outside of one T-shirt. Every bib number is between 1 and 1,000,000, inclusive.

For every T-shirt, print the bib number that should be visible, one per line, in input order.

If it is impossible, print -1.