Indiana Jones and the Lost Soccer Cup

In 1930 the first FIFA World Cup was held in Uruguay, where the host nation won the trophy in a dramatic final against Argentina. So much time has passed that myth and legend now surround that first World Cup. Some even claim that the original trophy awarded to Uruguay holds mythical powers and could grant any team the strength to win the World Cup. That cup has long been lost, and although its powers are almost certainly just stories, it remains an important artifact that belongs in a museum. Recovering it clearly calls for an expert.

The famous archaeologist and adventurer Indiana Jones has taken on this dangerous task and traveled to Uruguay to find the cup. His search has led him to an ancient underground cave system where the cup is rumored to be hidden. The caves are full of traps, and only his instinct and his trusty whip have saved him from certain death. He has now reached a mysterious, enormous gate and suspects that the cup lies behind it. Unfortunately, the gate is shut tight.

The gate is covered with switches and levers, each labeled with letters and numbers. As you might guess, the gate opens only if the switches and levers are operated in the correct order — but beware: anyone who gets the order wrong is doomed.

Luckily, while exploring the caves Indy found several encrypted hints about the correct sequence. One reads: “The faithful know that X comes before O.” Another warns: “Under no circumstances touch ∆ unless Θ has already been moved!” These clues constrain the order, but there are many switches and levers and many clues. Indy needs help.

Given all of the hints Indy has collected, can you determine the correct order in which to operate the levers and switches? Beware, though: Indy may have missed some hints, or misinterpreted some of them. Missing hints usually leave more than one possible sequence, while a misinterpretation leads to no possible sequence at all. You must detect these cases and warn him.

The first line contains the number of test cases $C$ $(C \le 30)$.

Each test case begins with a line containing two integers: the number of switches/levers $n$ $(1 \le n \le 10000)$ on the gate and the number of hints $h$ $(0 \le h \le 100000)$ that Indy has discovered. Each of the following $h$ lines contains two integers $a$ and $b$ $(1 \le a, b \le n,\ a \ne b)$, meaning that lever $a$ must be operated before lever $b$.

For each test case, output a single line. If there is exactly one valid order, print the numbers $1$ through $n$ in that order, separated by single spaces. If there is no valid order, print recheck hints instead. If more than one valid order is possible, print missing hints instead.