Race Bib Numbers
Time limit3sMemory limit512 MB
Given N T-shirts each printed with two candidate bib numbers, choose one number per shirt so all visible numbers are distinct, or print -1 if no such choice exists.
- Level
Hard8 of 10
- Topics
- Union-find, Graph, Greedy, Implementation
- Solved
- No attempts yet
Problem
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.
Input
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.
Output
For every T-shirt, print the bib number that should be visible, one per line, in input order.
If it is impossible, print -1.