K. 环基基环树
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

有一张无向连通简单图 $$$G$$$，它是一个基环树。也就是说，若 $$$G$$$ 有 $$$k$$$ 个点，则它恰好也有 $$$k$$$ 条边。

现在这张图发生了如下变异：

对于原图中的每个点 $$$x$$$，选择一个整数 $$$c_x \ge 3$$$，并将点 $$$x$$$ 替换成一个长度为 $$$c_x$$$ 的简单环 $$$C_x$$$。对于原图中的每一条边 $$$(u,v)$$$，在环 $$$C_u$$$ 上任选一个点，在环 $$$C_v$$$ 上任选一个点，并在这两个点之间连一条边。

不同的原边在同一个环上可以连接到同一个点，也可以连接到不同的点。保证变异后得到的图仍然是一个无向连通简单图。

现在给出变异后的图，你需要还原出任意一张与原图 $$$G$$$ 同构的基环树。

如果有多种答案，输出任意一种即可。

Input

第一行一个正整数 $$$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$$$。

Output

对于每组数据：

第一行输出一个整数 $$$k$$$，表示你还原出的基环树的点数。

接下来输出 $$$k$$$ 行，每行两个整数 $$$u,v$$$，表示你还原出的基环树中的一条无向边。

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

Example
Input
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
Output
3
1 2
1 3
2 3
4
1 3
2 3
2 4
3 4