In SUSTech, if you want to select a course,
you have to learn the prerequisite course at first. As you know, Itakejgo wants to
be a student in Department of CSE. He has to learn n courses. The prerequisite
information is given. Please find a way to select courses. If there are multiple ways, print the one with minimum alphabet order. Besides, the information may
be wrong. If you cannot find such a way to select courses, print “impossible” (without
quotes). The courses are labeled from 1 to n.
Note: the input guarantees that no courses are required the same course twice.
The first line will be an integer T. (1
<= T <= 500) T is the number of test cases.
For each test cast, the first line will two
integers n and m. (1 <= n <= 5000, 1 <= m <= 20000).
Then there will be m lines. Each line will
contain two integers x y. Means x is the prerequisite course of y. ( you have
to learn x before y)
For each test case, print a way to choose
course. If there are more than one ways, print the one with minimum alphabet
For the first sample, we can choose 1
first, then 2, then 3 … But we need to choose 8 before 7.
For the third sample, we cannot get a
solution. So the course may be wrong.