Bessie 有一张连通无向图 $G$，包含 $N$ 个编号为 $1\ldots N$ 的顶点和 $M$ 条边（$2\le N\le 10^5, N-1\le M\le \frac{N^2+N}{2}$）。$G$ 可以包含自环（从一个顶点连向其自身的边），但不包含重边（连接相同端点的多条边）。
对于每个 $1\le a\le N$ 和 $0\le b$，定义布尔函数 $f_G(a,b)$：如果存在一条从顶点 $1$ 到顶点 $a$、恰好经过 $b$ 条边的路径，则其值为真，否则为假。如果一条边被经过多次，则每次经过都计入边数。
Elsie 想模仿 Bessie。具体来说，她想构造一张无向图 $G'$，使得对于所有 $a$ 和 $b$ 都有 $f_{G'}(a,b)=f_G(a,b)$。
Elsie 想尽可能少费力，因此希望构造尽可能小的图。所以，你的任务是计算 $G'$ 中可能的最少边数。
每份输入包含 $T$（$1\le T\le 5\cdot 10^4$）组需要独立求解的测试数据。保证所有测试数据的 $N$ 之和不超过 $10^5$，$M$ 之和不超过 $2\cdot 10^5$。
输入格式
输入的第一行包含 $T$，表示测试数据的组数。
每组测试数据的第一行包含两个整数 $N$ 和 $M$。
每组测试数据接下来的 $M$ 行各包含两个整数 $x$ 和 $y$（$1\le x\le y\le N$），表示 $G$ 中存在一条连接 $x$ 和 $y$ 的边。
为了便于阅读，相邻两组测试数据之间用空行分隔。
输出格式
对于每组测试数据，在单独一行输出 $G'$ 中可能的最少边数。
样例
输入格式 1
2
5 5
1 2
2 3
2 5
1 4
4 5
5 5
1 2
2 3
3 4
4 5
1 5输出格式 1
4
5说明
在第一组测试数据中，Elsie 可以从 $G$ 出发，删去 $(2,5)$，得到 $G'$。她也可以构造包含以下边的图，因为她并不限于只从 $G$ 中删除边：
1 2 1 4 4 3 4 5
由于 $G'$ 也必须连通，Elsie 的答案显然不可能小于 $N-1$。
输入格式 2
7
8 10
1 2
1 3
1 4
1 5
2 6
3 7
4 8
5 8
6 7
8 8
10 11
1 2
1 5
1 6
2 3
3 4
4 5
4 10
6 7
7 8
8 9
9 9
13 15
1 2
1 5
1 6
2 3
3 4
4 5
6 7
7 8
7 11
8 9
9 10
10 11
11 12
11 13
12 13
16 18
1 2
1 7
1 8
2 3
3 4
4 5
5 6
6 7
8 9
9 10
9 15
9 16
10 11
11 12
12 13
13 14
14 15
14 16
21 22
1 2
1 9
1 12
2 3
3 4
4 5
5 6
6 7
7 8
7 11
8 9
8 10
12 13
13 14
13 21
14 15
15 16
16 17
17 18
18 19
19 20
20 21
20 26
1 2
1 5
1 6
2 3
3 4
4 5
4 7
6 8
8 9
8 11
8 12
8 13
8 14
8 15
8 16
8 17
9 10
10 18
11 18
12 19
13 20
14 20
15 20
16 20
17 20
19 20
24 31
1 2
1 7
1 8
2 3
3 4
4 5
5 6
6 7
6 9
8 10
10 11
10 16
10 17
10 18
10 19
10 20
11 12
12 13
13 14
14 15
15 16
15 17
15 18
15 19
15 20
15 21
15 22
15 23
15 24
21 22
23 24输出格式 2
10
11
15
18
22
26
31说明
在这些测试数据中，Elsie 都无法比 Bessie 做得更好。
- 输入文件 3 中的所有测试数据满足 $N\le 5$。
- 输入文件 4–5 中的所有测试数据满足 $M=N$。
- 对于输入文件 6–9 中的所有测试数据，如果并非对所有 $b$ 都有 $f_G(x,b)=f_G(y,b)$，则存在 $b$，使得 $f_G(x,b)$ 为真且 $f_G(y,b)$ 为假。
- 输入文件 10–15 中的所有测试数据满足 $N\le 10^2$。
- 输入文件 16–20 中的测试数据没有额外限制。
题目作者：Benjamin Qi