Bessie 有一个连通无向图 G。G 有 N 个编号为 1…N 的结点，以及 M 条边（2≤N≤10$^5$,N−1≤M≤ ${ N^2+N \over 2}$）。G 有可能包含自环（一个结点连到自身的边），但不包含重边（连接同一对结点的多条边）。令 f$_G$(a,b) 为一个布尔函数，对于每一个 1≤a≤N 和 0≤b，如果存在一条从结点 1 到结点 a 的路径恰好经过了 b 条边，则函数值为真，否则为假。如果一条边被经过了多次，则这条边会被计算相应的次数。

Elsie 想要复制 Bessie。具体地说，她想要构造一个无向图 G'，使得对于所有的 a 和 b，均有 f$_{G′}$(a,b)=f$_G$(a,b)。

Elsie 想要进行最少数量的工作，所以她想要构造最小可能的图。所以，你的工作是计算 G′ 的边数的最小可能值。

每个输入包含 T（1≤T≤5⋅10$^4$）组独立的测试用例。保证所有测试用例中的 N 之和不超过 10$^5$，且所有测试用例中的 M 之和不超过 2⋅10$^5$。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 T，为测试用例的数量。每个测试用例的第一行包含两个整数 N 和 M。

每个测试用例的以下 M 行每行包含两个整数 x和 y（1≤x≤y≤N），表示 G 中存在一条连接 x 与 y 的边。

为提高可读性，相邻的测试用例之间用一个空行隔开。

输出格式（输出至终端 / 标准输出）：

对每个测试用例，输出一行，为 G′ 中的边数的最小可能值。

输入样例：

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

输出样例：

4
5

在第一个测试用例中，Elsie 可以通过从 G 中移除(2,5) 来构造得到 G′。或者，她也可以构造一张包含以下边的图，因为她并未被限制只能从 G 中移除边：

1 2
1 4
4 3
4 5

Elsie 显然不能得到比 N−1 更优的解，因为 G′ 一定也是连通的。

输入样例：

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

输出样例：

10
11
15
18
22
26
31

在以上这些测试用例中，Elsie 都不能做得比 Bessie 更优。

测试点性质：

• 测试点 3 的所有测试用例满足 N≤5。
• 测试点 4-5 的所有测试用例满足 M=N。
• 测试点 6-9 的所有测试用例中，如果并非对于所有的 b 均有 fG'(x,b)=fG(y,b)，则存在 b 使得 fG'(x,b) 为真且 fG(y,b) 为假。
• 测试点 10-15 中的所有测试用例满足 N≤10$^2$。
• 测试点 16-20 中的测试用例没有额外限制。