Problem $3(7=7)$ Reconstructing a total order

A group of n runners finished a close race. Unfortunately, the officials at the finish line were unable to note

down the order in which the racers finished. Each runner, however, noted the jersey number of the runner

finishing immediately ahead of her or him. $($There were no ties.$)$ The race officials ask each runner to give

an ordered pair, containing two pieces of information: $($a$)$ first, his or her own jersey number and $($b$)$ second,

the jersey number of the runner who finished immediately ahead of him or her. The winner of the race, who

did not see anybody finish ahead of her, enters $$ for $($b$).$

You have been asked to design an algorithm that takes as input the n pairs and returns the order in which

the runners finished the race. Assume each runner is honest.

Give a deterministic $\backslash$Theta $($n log n$)$ time algorithm, and justify the running time of the algorithm. $($Hint: Use

sorting.