{"raw_statement":[{"iden":"problem statement","content":"You are given a graph $G$ consisting of $N$ vertices numbered $1, 2, \\ldots, N$. Initially, $G$ has no edges.\nYou will add $M$ undirected edges to $G$. The final shape of the graph is predetermined, and the $i$\\-th edge to be added $(1 ≤ i ≤ M)$ connects vertices $u_i$ and $v_i$. We will refer to this as edge $i$.  \nIt is guaranteed that the resulting graph will be simple.\nDetermine if there exists a permutation $(P_1, P_2, \\ldots, P_M)$ of $(1, 2, \\ldots, M)$ that satisfies the following conditions, and if such a permutation exists, show an example.\n\n> **Conditions**\n> You must be able to add all $M$ edges to $G$ by following this procedure:\n> \n> *   For $i = 1, 2, \\dots, M$, repeat the following:\n>     1.  If there is already a cycle in $G$ containing either vertex $u_{P_i}$ or vertex $v_{P_i}$, the condition is not satisfied, and the procedure ends.\n>     2.  Add edge $P_i$ (the undirected edge connecting $u_{P_i}$ and $v_{P_i}$) to $G$.\n\nYou are given $T$ test cases; solve each of them.\nWhat is a cycle? A cycle in $G$ is defined as a sequence of vertices $(v_0, \\dots, v_{L - 1})$ and a sequence of edges $(e_0, \\dots, e_{L - 1})$ that satisfy the following conditions:\n\n*   $L \\ge 1$\n*   $i \\neq j \\implies v_i \\neq v_j, e_i \\neq e_j$\n*   For $0 \\le i \\le L - 2$, edge $e_i$ connects vertices $v_i$ and $v_{i+1}$\n*   Edge $e_{L-1}$ connects vertices $v_{L-1}$ and $v_0$\n\nWhat does it mean for a graph to be simple? A graph $G$ is simple if it contains no self-loops or multiple edges."},{"iden":"constraints","content":"*   All input values are integers.\n*   $1 \\le T \\le 2000$\n*   For each test case:\n    *   $2 \\le N \\le 4000$\n    *   $1 \\le M \\le 4000$\n    *   $1 \\le u_i, v_i \\le N\\ (1 ≤ i ≤ M)$\n    *   The graph formed by adding all given edges is simple.\n*   The sum of $N$ over all test cases is at most $4000$.\n*   The sum of $M$ over all test cases is at most $4000$."},{"iden":"subtasks","content":"$30$ points will be awarded for passing the test set satisfying:\n\n*   $T \\le 50$\n*   For each test case:\n    *   $N \\le 100$\n    *   $M \\le 100$\n*   The sum of $N$ over all test cases is at most $100$.\n*   The sum of $M$ over all test cases is at most $100$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\text{case}_2$\n$\\vdots$\n$\\text{case}_T$\n\nHere, $\\text{case}_i\\ (1 ≤ i ≤ T)$ represents the $i$\\-th test case. Each test case is given in the following format:\n\n$N$ $M$\n$u_1$ $v_1$\n$u_2$ $v_2$ \n$\\vdots$\n$u_M$ $v_M$"},{"iden":"sample input 1","content":"1\n4 4\n1 2\n2 3\n3 4\n4 2"},{"iden":"sample output 1","content":"2 4 1 3\n\nThe given graph has the following shape:\n![image](https://img.atcoder.jp/ttpc2024_1/efcd772696bd0c92c27611b554a4d94b.png)\nIf we add the edges in the order $P = (1, 2, 3, 4)$, the conditions are satisfied as shown below:\n![image](https://img.atcoder.jp/ttpc2024_1/f639f61a8c21e023b412bb9d1f8c4cca.png) ![image](https://img.atcoder.jp/ttpc2024_1/d6307590977040bdaea3733c0df34398.png)\nThus, `1 2 3 4` is one valid output.\nHowever, if we add edges in the order $P = (2, 3, 4, 1)$, a cycle containing vertex $2$ is created before edge $1$ can be added, so the conditions are not satisfied.\n![image](https://img.atcoder.jp/ttpc2024_1/d7e2277adb8c0aace5f07f25a6cf2569.png) ![image](https://img.atcoder.jp/ttpc2024_1/11d01a954d01e5ea030492db5eefd3f8.png)\nOther valid outputs include $P = (1, 4, 3, 2)$ or $P = (2, 4, 1, 3)$."},{"iden":"sample input 2","content":"4\n4 5\n1 2\n2 3\n3 4\n3 1\n1 4\n5 3\n1 2\n2 3\n3 4\n9 10\n3 5\n1 8\n5 8\n4 9\n6 7\n7 9\n1 2\n1 4\n2 4\n4 6\n8 10\n1 4\n3 8\n2 5\n3 4\n1 5\n5 8\n2 8\n5 7\n4 5\n3 7"},{"iden":"sample output 2","content":"\\-1\n3 2 1\n4 10 2 8 7 9 6 5 3 1\n-1\n\nIf no valid $P$ exists, output `-1`. Note that the graph is not necessarily connected."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}