题目描述

有一张无向连通简单图 $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$，表示你还原出的基环树中的一条无向边。

你的输出图只要与某个合法原图同构即可，点的编号和边的顺序任意。

2
9 12
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
1 4
2 7
5 8
12 16
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
10 11
11 12
12 10
1 4
5 7
8 2
6 10

3
1 2
1 3
2 3
4
1 3
2 3
2 4
3 4