Bessie 拥有一个连通的无向图 $G$，包含 $N$ 个顶点（编号为 $1\ldots N$）和 $M$ 条边（$2\le N\le 10^5, N-1\le M\le \frac{N^2+N}{2}$）。$G$ 可能包含自环（从节点指向自身的边），但没有重边（连接相同端点的多条边）。

令 $f_G(a,b)$ 为一个布尔函数，当且仅当存在一条从顶点 $1$ 到顶点 $a$ 且恰好经过 $b$ 条边的路径时，该函数为真（对于所有 $1\le a\le N$ 和 $0\le 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 中的测试用例没有额外限制。