Read problems statements in mandarin chinese, russian and vietnamese as well.

Consider a sequence of positive integers A = (A_{1}, A_{2}, ... , A_{N}), and another sequence B = (B_{1}, B_{2}, ... , B_{M}). We say that B is a subsequence of A, if B can be written as (Ai_{1}, Ai_{2}, ... , Ai_{M}), where 1 ≤ i_{1} < i_{2} ... < i_{M} ≤ N. If B is a subsequence of A, there could be multiple ways to write it in such a manner, and among all those ways, we choose the way which minimizes i_{M}. We call this minimized i_{M} to be f(B). Note that in the definition of f(B), we are assuming that A is a constant. Also, when B is the empty sequence, it is considered to be a subsequence of A, and f(B) would then be 0.

Now, given A, we will construct a graph G which has N + 1 nodes and labeled directed edges. The nodes are {V_{0}, V_{1}, ..., V_{N}}. If there are two subsequences of A: C_{1} and C_{2}, such that C_{2} is obtained by appending the integer b at the end of C_{1}, and f(C_{1}) ≠ f(C_{2}), then the edge ( Vf(C_{1}), b, Vf(C_{2}) ) is added to the graph G if it is not already present in the graph. (Note that even if an edge with a different label is already present, this edge is added. Just that there will not be multiple edges from one vertex to another with the same label). The edge (V_{i}, b, V_{j}) means that it is a directed edge from V_{i} to V_{j}, and it has the label b.

Chef constructed this graph, but then lost the sequence A, as well as all the labels on the graph. So all he has left is a directed graph (with possibly multiple edges from one vertex to another), and now he wants to find the sequence A. Since there could be many such sequences which fit the graph, he wants to find the lexicographically smallest such sequence. Help Chef in finding this.

------ Input ------

The first line contains a single integer, T, which is the number of testcases. The description of each testcase follows.
The first line of each testcase contains two integers, N and M. This means that the input graph has vertices {V_{0}, V_{1}, ..., V_{N}} and M directed multi-edges.
The i-th of the next M lines contains two integers, x_{i} and y_{i}, which denote that there is a directed edge from Vx_{i} to Vy_{i}.

------ Output ------

For each testcase, output a single line which contains N positive integers which denote the lexicographically smallest sequence which can lead to the construction of the inputted graph. Or, if such a sequence does not exist, output -1.

------ Constraints ------

$1 ≤ T ≤ 10$
$1 ≤ N, M ≤ 10^{5}$
$0 ≤ x_{i}, y_{i} ≤ N$

------ Subtasks ------

$Subtask 1 (30 points) : N, M ≤ 10^{3}$
$Subtask 2 (70 points) : Original constraints$

----- Sample Input 1 ------
2

5 11

0 1

0 2

0 5

2 3

2 5

1 3

1 5

1 2

3 4

3 5

4 5

3 4

0 3

2 3

1 2

0 1
----- Sample Output 1 ------
1 2 1 1 3

-1
----- explanation 1 ------
Testcase 1:
Let us consider the sequence A = (1, 2, 1, 1, 3).
f(empty string) = 0, and f( (1) ) = 1. (1) can be obtained by appending 1 to the empty string. Hence there should be an edge from V0 to V1 with the label 1.
Similarly, f( (1, 2, 1) ) = 3 and f( (1, 2, 1, 3) ) = 5. Hence there should be an edge from V3 to V5 with label 3.
By looking at all such possible pairs of valid subsequences, we can see that the edges obtained from this A exactly match the edges given in the input graph. And this is the lexicographically smallest such sequence. Hence the answer is this sequence.

Testcase 2:
There is no sequence which leads to the construction of this graph. Hence the answer is -1.

见题面

见题面