Just Half is Enough
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Jacob is studying graph theory. Today he learned that a topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge $$$(u, v)$$$ from vertex $$$u$$$ to vertex $$$v$$$, $$$u$$$ comes before $$$v$$$ in the ordering.

It is well-known that topological orderings exist only for graphs without cycles. But how do we generalize this concept for arbitrary graphs?

Jacob came up with the concept of a half-topological ordering: a linear ordering of the graph's vertices such that for at least half of all directed edges $$$(u, v)$$$ in the graph, $$$u$$$ comes before $$$v$$$ in the ordering.

In other words, if the graph has $$$m$$$ edges, and for a particular ordering, $$$k$$$ of them satisfy the condition above, then the ordering is called half-topological if $$$k \ge \lceil \frac{m}{2} \rceil$$$.

Help Jacob find any half-topological ordering of the given graph, or report that none exist.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$, denoting the number of vertices and the number of edges in the graph ($$$2 \le n \le 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$).

The $$$i$$$-th of the following $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$, describing an edge from vertex $$$u_i$$$ to vertex $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$). The graph does not contain multiple edges: each directed edge $$$(u, v)$$$ appears at most once. However, having both edges $$$(u, v)$$$ and $$$(v, u)$$$ is allowed.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer $$$-1$$$ if the required half-topological ordering does not exist.

Otherwise, print $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$, describing the ordering of the given graph ($$$1 \le p_i \le n$$$). For at least $$$\lceil \frac{m}{2} \rceil$$$ of the edges $$$(u_i, v_i)$$$, integer $$$u_i$$$ must come before integer $$$v_i$$$ in this list. If there are multiple answers, print any of them.

Example

Input
2
3 3
1 2
2 3
3 1
5 6
4 2
2 1
4 3
1 4
3 2
3 5
Output
1 2 3
3 1 5 4 2