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 使用更少的邊。

題目作者：Benjamin Qi