{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eWe say an undirected graph is a planar graph, if it exists a way to draw it on a planar, such that no two edges have intersection \u003cb\u003eexcept the endpoint\u003c/b\u003e. For example, the graph below is a planar graph:\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/d25f92854e185d8480030ffbeb4bb0ee?v\u003d1714475208\"\u003e\u003c/center\u003e\u003cbr\u003eBut this graph below is \u003cb\u003enot\u003c/b\u003e a planar graph, since it can be proved that no matter how to draw this graph on a planar, at least two edges have intersection which is not an endpoint: \u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/32e39d231528342f8631d44f89fd9e11?v\u003d1714475208\"\u003e\u003c/center\u003e\u003cbr\u003eFor a planar graph, it has some areas separated by edges. For example, the planar graph below has $4$ areas (Note that the area $1$ is the infinite planar outside):\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/b1918a62dc4b362006c718ba77239579?v\u003d1714475208\"\u003e\u003c/center\u003e\u003cbr\u003eGive you a planar graph with $n$ vertices and $m$ edges. Each area sets a country. You are the designer and you want to build some tunnels on the edges such that: From one city, you can travel to any other city by going through some tunnels or passing some cities(i.e. you can\u0027t cross one edge unless it sets a tunnel). For example, for the graph above, you can build tunnels like this:\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/d051fa2cb6883005ab294efbb6fdacff?v\u003d1714475208\"\u003e\u003c/center\u003e\u003cbr\u003eIn the picture above, you can travel from city $2$ to city $3$ by going through tunnel $1$, passing the city $1$, then going through tunnel $3$, passing the city $4$, finally going through tunnel $2$, and you can arrive to city $3$. You can check that from any city you can travel to any other city.\u003cbr\u003e\u003cbr\u003eYou want the number of tunnels as small as possible. Print the minimum number of tunnels and the ID of edges you build tunnel on.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains one integer $T(1\\le T\\le 15)$, described the number of test cases.\u003cbr\u003e\u003cbr\u003eFor each test case: \u003cbr\u003e\u003cbr\u003eThe first line contains two integers $n, m(1\\le n\\le 10^5, 0\\le m\\le 2\\times 10^5)$ separated by a space, described the number of vertices and edges.\u003cbr\u003e\u003cbr\u003eNext $m$ lines, the $i$-th line contains two integers $u, v(1\\le u,v\\le n)$, separated by a space, described the endpoint of the $i$-th edge. The ID of the $i$-th edge is $i$.\u003cbr\u003e\u003cbr\u003eIt is guaranteed that the given graph is a planar graph. \u003cb\u003eBut this graph may have self-loop, parallel edge and the graph may not connected\u003c/b\u003e."}},{"title":"Output","value":{"format":"HTML","content":"The output contains $2T$ lines.\u003cbr\u003e\u003cbr\u003eFor each test case:\u003cbr\u003e\u003cbr\u003eThe first line contains one integer $f$, described the minimum number of tunnels you have to build.\u003cbr\u003e\u003cbr\u003eThe second lines contains $f$ integers separated by spaces, the $i$-th integer described the ID of edges the $i$-th tunnel built on.\u003cbr\u003e\u003cbr\u003eIf for a fixed minimum number of tunnels, it has many ways to build the tunnels, \u003cb\u003eprint the lexicographically smallest answer\u003c/b\u003e."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n5 7\r\n1 1\r\n1 2\r\n1 3\r\n3 4\r\n3 4\r\n2 4\r\n2 5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n1 2 4 \r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}