P16967 [SCCPC 2026] 环基基环树

有一张无向连通简单图 $G$，它是一个基环树。也就是说，若 $G$ 有 $k$ 个点，则它恰好也有 $k$ 条边。 现在这张图发生了如下变异： 对于原图中的每个点 $x$，选择一个整数 $c_x \ge 3$，并将点 $x$ 替换成一个长度为 $c_x$ 的简单环 $C_x$。对于原图中的每一条边 $(u,v)$，在环 $C_u$ 上任选一个点，在环 $C_v$ 上任选一个点，并在这两个点之间连一条边。 不同的原边在同一个环上可以连接到同一个点，也可以连接到不同的点。保证变异后得到的图仍然是一个无向连通简单图。 现在给出变异后的图，你需要还原出任意一张与原图 $G$ 同构的基环树。 如果有多种答案，输出任意一种即可。

第一行一个正整数 $t$（$1 \le t \le 10^5$），表示数据组数。 对于每组数据： 第一行两个整数 $n,m$（$9 \le n \le 10^6,\ 12 \le m \le 10^6$），表示变异后图的点数和边数。 接下来 $m$ 行，每行两个整数 $u,v$（$1 \le u,v \le n,\ u \ne v$），表示变异后图中的一条无向边。 保证输入图是无向连通简单图，并且一定可以由某张基环树按照题目中的规则变异得到。 保证所有数据中，$\sum n \le 10^6,\ \sum m \le 1333333$。

对于每组数据： 第一行输出一个整数 $k$，表示你还原出的基环树的点数。 接下来输出 $k$ 行，每行两个整数 $u,v$，表示你还原出的基环树中的一条无向边。 你的输出图只要与某个合法原图同构即可，点的编号和边的顺序任意。