Netflix

Netflix stocks are approaching an all-time low, so the company is forced to take desperate steps. The plan is to go back to the basics and hire traveling salesmen that will go door to door and will try to convince possible clients to subscribe to the service.

Your friend was out of job for some time now (in case making Tik-Tok videos doesn't count as one), so in order to pay the bills, he decided to try out this salesman thing at Netflix. He was assigned to a strange neighborhood, with one-way streets only, and having the property that starting from any house, there is no way to get back there. Your friend needs your help to determine if it's possible for him to knock on all the doors in the neighborhood.

Input Specification

The first line of the input contains t, the number of test cases to follow (1 ≤ t ≤ 20). Each test case starts with a line containing n, the number of houses in the neighborhood (1 ≤ n ≤ 100 000), and m, the number of streets (1 ≤ m ≤ 1 000 000). The following m lines contain two numbers x and y, with the meaning that there is a street going from house x to house y. The houses are numbered from 1 to n. Whitespaces can occur freely in the input.

Output Specification

For each test case, you must output a single line. If your friend can visit all the houses, output a possible order in which he can visit them. Otherwise output -1.

Sample Input

1. 4
3. 3 2
4. 1 3
5. 3 2
7. 4 4
8. 4 2
9. 2 3
10. 4 1
11. 1 3
13. 4 2
14. 1 2
15. 3 4
17. 5 6
18. 2 1
19. 1 3
20. 3 5
21. 1 4
22. 2 4
23. 4 3

download as text file

Output for Sample Input

1. 1 3 2
2. -1
3. -1
4. 2 1 4 3 5

download as text file