U626061 重建道路(rebuild)

10.28 模拟赛 T1

给出 $n$ 个点 $m$ 条边的双向图 $G$，每次操作你可以重建一条边：重新选择一条边的起点终点。 请问最少需要多少次操作才能将图 $G$ 变为一个连通图，并请你输出字典序最小的方案。

第一行包含 $1$ 个整数 $T$，代表有 $T$ 组数据。 每组数据首先一行包含 2个整数 $n$,$m$ 。 接下来 $m$ 行，每行 2个整数 $(u,v)$，代表一条连接 $(u,v)$ 的双向边，数据保证**没有自环**。

对于每组数据：首先一个整数 $t$，代表最小操作数。 接下来输出 行，每行 $4 $ 个整数 $(i,j,u,v)$ 代表一次操作，表示将 $(i,j)$ 这条边重建为 $(u,v)$ 。若有多解，**输出字典序最小的**；若无解，输出` -1 `。

对于测试点 1-4 ，$n\leqslant10,m\leqslant50$ 对于测试点 5-6 ，$n\leqslant1000,m=n-1$ 对于测试点 7-8 ，只有 $(i,i+1)$ 之间有边 对于测试点 9-10 ，无特殊限制 对于 100% 的数据，$1\leqslant n\leqslant10^5,1\leqslant n\leqslant2\times10^5,1\leqslant u,v\leqslant n$