P16967 [SCCPC 2026] Cycle-of-Cycles Unicyclic Tree.

There is an undirected connected simple graph $G$, which is a unicyclic tree. That is, if $G$ has $k$ vertices, then it also has exactly $k$ edges. Now the graph undergoes the following mutation: For each original vertex $x$, choose an integer $c_x \ge 3$, and replace vertex $x$ with a simple cycle $C_x$ of length $c_x$. For each original edge $(u,v)$, choose any vertex on the cycle $C_u$ and any vertex on the cycle $C_v$, and add an edge between these two chosen vertices. Different original edges may connect to the same vertex on the same cycle, or to different vertices. It is guaranteed that the resulting graph after mutation is still an undirected connected simple graph. Now you are given the mutated graph. You need to restore any unicyclic tree that is isomorphic to the original graph $G$. If there are multiple answers, output any one of them.

The first line contains a positive integer $t$ ($1 \le t \le 10^5$), denoting the number of test cases. For each test case: The first line contains two integers $n, m$ ($9 \le n \le 10^6,\ 12 \le m \le 10^6$), denoting the number of vertices and edges in the mutated graph. The next $m$ lines each contain two integers $u, v$ ($1 \le u, v \le n,\ u \ne v$), denoting an undirected edge in the mutated graph. It is guaranteed that the input graph is an undirected connected simple graph, and it can definitely be obtained by mutating some unicyclic tree according to the rules in the statement. It is guaranteed that across all test cases, $\sum n \le 10^6$ and $\sum m \le 1333333$.

For each test case: The first line outputs an integer $k$, denoting the number of vertices in the unicyclic tree you restored. Then output $k$ lines, each containing two integers $u, v$, denoting an undirected edge in the unicyclic tree you restored. Your output graph only needs to be isomorphic to some valid original graph. The vertex labels and the order of edges can be arbitrary.

Translated by ChatGPT 5