C. Disney Land
time limit per test
3 seconds
memory limit per test
256 megabytes
input
disney.in
output
standard output

"I found Donald Duck, Micky Mouse, and Minnie Mouse. What are you doing? We're not in Disney Land" said Omda.

There was an invasion of Sasa's studio by Disney characters. Help us, God!!.

Moda wanted to find out the order in which the characters entered the studio so that, he could hunt them down.

Disney characters are represented by a permutation of $$$N$$$ integers.

A permutation is an array consisting of $$$N$$$ distinct integers from $$$1$$$ to $$$N$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$N=3$$$ but there is $$$4$$$ in the array)

Additionally, you are given $$$M$$$ restrictions. You want to recover the lexicographically smallest permutation under those restrictions or report that there isn't any valid permutation.

The $$$i^{th}$$$ restriction says that $$$P_{X_i} \neq Y_i$$$.

Please help Moda recover the permutation of Disney characters.

Input

The first line contains the number of test cases $$$T$$$ $$$(1 \leq T \leq 10^5)$$$.

The first line of each test case contains two integers $$$N$$$ and $$$M$$$ $$$(1 \leq N \leq 10^3)$$$ $$$(1 \leq M \leq 10^5)$$$.

The following $$$M$$$ lines of each test case contains two space-separated integers $$$X_i$$$ and $$$Y_i$$$ $$$(1 \leq X_i,Y_i \leq N)$$$

It is guaranteed that there is that for any $$$1 \leq i \le j \leq M$$$ either $$$X_i \neq X_j$$$ or $$$Y_i \neq Y_j$$$.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$10^3$$$.

It is guaranteed that the sum of $$$M$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, print the answer $$$P$$$ or $$$-1$$$ if there is no answer.

Example
Input
2
5 5
1 1
1 2
1 3
2 2
2 3

5 5
1 5
2 5
3 5
4 5
5 5
Output
4 1 2 3 5
-1