{"problem":{"name":"[ICPC 2020 Nanjing R] Degree of Spanning Tree","description":{"content":"Given an undirected connected graph with $n$ vertices and $m$ edges, your task is to find a spanning tree of the graph such that for every vertex in the spanning tree its degree is not larger than $\\f","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9625"},"statements":[{"statement_type":"Markdown","content":"Given an undirected connected graph with $n$ vertices and $m$ edges, your task is to find a spanning tree of the graph such that for every vertex in the spanning tree its degree is not larger than $\\frac{n}{2}$.\n\nRecall that the degree of a vertex is the number of edges it is connected to.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains two integers $n$ and $m$ ($2 \\le n \\le 10^5$, $n-1 \\le m \\le 2 \\times 10^5$) indicating the number of vertices and edges in the graph.\n\nFor the following $m$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \\le u_i, v_i \\le n$) indicating that there is an edge connecting vertex $u_i$ and $v_i$. Please note that there might be self loops or multiple edges.\n\nIt's guaranteed that the given graph is connected. It's also guaranteed that the sum of $n$ of all test cases will not exceed $5 \\times 10^5$, also the sum of $m$ of all test cases will not exceed $10^6$.\n\n## Output\n\nFor each test case, if such spanning tree exists first output ``Yes`` in one line, then for the following $(n-1)$ lines print two integers $p_i$ and $q_i$ on the $i$-th line separated by one space, indicating that there is an edge connecting vertex $p_i$ and $q_i$ in the spanning tree. If no valid spanning tree exists just output ``No`` in one line.\n\n[samples]\n\n## Note\n\n### Note\n\nFor the first sample test case, the maximum degree among all vertices in the spanning tree is 3 (both vertex 1 and vertex 4 has a degree of 3). As $3 \\le \\frac{6}{2}$ this is a valid answer.\n\nFor the second sample test case, it's obvious that any spanning tree will have a vertex with degree of 2, as $2 > \\frac{3}{2}$ no valid answer exists.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9625","tags":["图论","2020","Special Judge","O2优化","构造","ICPC","南京"],"sample_group":[["2\n6 9\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4\n4 5\n4 6\n4 6\n3 4\n1 3\n2 3\n3 3\n1 2\n","Yes\n1 2\n1 3\n1 4\n4 5\n4 6\nNo\n"]],"created_at":"2026-03-03 11:09:25"}}