10791079 SUSTech Online Judge
Problem 1079 --Course Selection

1079: Course Selection

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1479  Solved: 432
[Submit][Status][Web Board]

Description

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.

Input

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)

Output

For each test case, print a way to choose course. If there are more than one ways, print the one with minimum alphabet order.

Sample Input

3
8 6
1 2
1 3
1 4
5 6
6 7
8 7
4 3
1 2
3 2
2 4
3 3
1 2
2 3
3 1

Sample Output

1 2 3 4 5 6 8 7
1 3 2 4
impossible

HINT


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.

Source

 

[Submit][Status]