Problem B
Reactivity Series

Picture by matthewvenn

During his physics research, the Ph.D. candidate Ulf invented some new metals as the existing ones were not good enough. He is now investigating the properties of the new metals, and is interested in knowing how reactive they are, so that he won’t blow his house up while mixing them with water.

He wants to order the metals by reactivity into a so-called reactivity series, where the metal with the highest reactivity comes first, and lowest reactivity comes last. Normally, Ulf (who is also proficient in computer science) would make an optimal scheme of measurements such that he has to make as few measurements as possible to determine such a series. Unfortunately, having invented entirely new substances, he was eager to begin experimenting, and randomly took pairs of elements and compared their reactivity.

Ulf’s experiments consisted of taking two different metals, and testing which one had the highest reactivity. You may assume Ulf never makes mistakes in his experiments, and that the reactivity is distinct for all elements (i.e. for any pair of metals, one will always be the more reactive one). This relation is such that if metal $A$ is more reactive than metal $B$ which in turn is more reactive than metal $C$, it follows that $A$ is more reactive than $C$ as well.

Before continuing his experiments, he is wondering whether the measurements he already has are enough to determine a unique reactivity series of all his metals.


The first line will consist of two integers $1 \le N \le 1\, 000$, the number of metals Ulf had discovered and $0 \le K \le \frac{N(N-1)}{2}$, the number of experiments Ulf performed. This is followed by $K$ lines, each consisting of two space separated integers $0 \le A \not= B \le N-1$, stating that the $A$:th metal has a higher reactivity than the $B$:th metal. The metals are numbered from 0 to $N-1$.


Output consists of $N$ integers from 0 to $N-1$, creating a reactivity series. The number of the metal with highest reactivity is the first one, with every following metal being of lower reactivity than the previous one. If it is impossible to construct a unique series containing all the metals, output the message "back to the lab" instead.

Sample Input 1 Sample Output 1
2 1
0 1
0 1 
Sample Input 2 Sample Output 2
4 4
0 1
0 2
2 3
1 3
back to the lab

Please log in to submit a solution to this problem

Log in