{"extraResources":{"example.01.mu":"TVXzATINCiFjMTszIDMNCjEgMg0KMiAzDQozIDENCiFjMjs1IDYNCjQgMg0KMiAxDQo0IDMNCjEgNA0KMyAyDQozIDUNCg=="},"scoring":null,"notes":"","legend":"Jacob is studying graph theory. Today he learned that a \\textit{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.\r\n\r\nIt is well-known that topological orderings exist only for graphs without cycles. But how do we generalize this concept for arbitrary graphs?\r\n\r\nJacob came up with the concept of a \\textit{half-topological ordering}: a linear ordering of the graph's vertices such that \\textbf{for at least half} of all directed edges $(u, v)$ in the graph, $u$ comes before $v$ in the ordering.\r\n\r\nIn 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 \\textit{half-topological} if $k \\ge \\lceil \\frac{m}{2} \\rceil$.\r\n\r\nHelp Jacob find any half-topological ordering of the given graph, or report that none exist.","authorLogin":"tourist","language":"english","timeLimit":2000,"output":"For each test case, print a single integer $-1$ if the required half-topological ordering does not exist.\r\n\r\nOtherwise, 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.","inputFile":"stdin","outputFile":"stdout","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.\r\n\r\nThe 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$).\r\n\r\nThe $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.\r\n\r\nIt 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$.","authorName":"Gennady Korotkevich","sampleTests":[{"output":"1 2 3\r\n3 1 5 4 2\r\n","input":"2\r\n3 3\r\n1 2\r\n2 3\r\n3 1\r\n5 6\r\n4 2\r\n2 1\r\n4 3\r\n1 4\r\n3 2\r\n3 5\r\n","inputFile":"example.01","outputFile":"example.01.a"}],"name":"Just Half is Enough","interaction":null,"memoryLimit":1073741824,"tutorial":"{\r\n    \\parindent=1cm\r\n    \\begin{tabular}{l@{\\extracolsep{1cm}}l}\r\n         Идея: & Артем Васильев\\\\\r\n         Разработка: & Геннадий Короткевич\\\\\r\n     \\end{tabular}\r\n}\r\n\r\nНайдём $k$~--- число рёбер, удовлетворяющих условию $u_i < v_i$. Если $k \\ge \\lceil \\frac{m}{2} \\rceil$, выведем перестановку $1, 2, \\ldots, n$. В противном случае, выведем перестановку $n, n-1, \\ldots, 1$.\r\n\r\nПоскольку каждое ребро удовлетворяет либо условию $u_i < v_i$, либо условию $u_i > v_i$, в сумме перестановки $1, 2, \\ldots, n$ и $n, n-1, \\ldots, 1$ имеют ровно $m$ подходящих рёбер. А значит, хотя бы одна из них будет иметь хотя бы половину от $m$.\r\n\r\nТак как это верно для любой пары перестановок $p_1, p_2, \\ldots, p_n$ и $p_n, p_{n-1}, \\ldots, p_1$, в качестве альтернативного решения можно генерировать случайные перестановки, пока не найдём ту, которая сработает. В среднем понадобится не более $2$ итераций."}