Bessie có một đồ thị vô hướng, liên thông $G$ gồm $N$ đỉnh được đánh số $1\ldots N$ và $M$ cạnh ($2\le N\le 10^5, N-1\le M\le \frac{N^2+N}{2}$). $G$ có thể chứa khuyên (cạnh nối một đỉnh với chính nó), nhưng không có cạnh song song (nhiều cạnh nối cùng một cặp đầu mút).

Với mỗi $1\le a\le N$ và $0\le b$, gọi $f_G(a,b)$ là hàm Boolean nhận giá trị đúng nếu tồn tại một đường đi từ đỉnh $1$ đến đỉnh $a$ đi qua đúng $b$ cạnh, và nhận giá trị sai trong trường hợp ngược lại. Nếu một cạnh được đi qua nhiều lần, nó được tính vào số cạnh đúng bằng số lần đó.

Elsie muốn bắt chước Bessie. Cụ thể, cô ấy muốn xây dựng một đồ thị vô hướng $G'$ sao cho $f_{G'}(a,b)=f_G(a,b)$ với mọi $a$ và $b$.

Elsie muốn làm ít việc nhất có thể, nên cô ấy muốn xây dựng đồ thị nhỏ nhất có thể. Vì vậy, nhiệm vụ của bạn là tính số cạnh nhỏ nhất có thể của $G'$.

Mỗi dữ liệu vào chứa $T$ ($1\le T\le 5\cdot 10^4$) bộ test cần được giải độc lập. Đảm bảo rằng tổng $N$ của tất cả các bộ test không vượt quá $10^5$, và tổng $M$ của tất cả các bộ test không vượt quá $2\cdot 10^5$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa $T$, số bộ test.

Dòng đầu tiên của mỗi bộ test chứa hai số nguyên $N$ và $M$.

$M$ dòng tiếp theo của mỗi bộ test, mỗi dòng chứa hai số nguyên $x$ và $y$ ($1\le x\le y\le N$), cho biết có một cạnh nối $x$ và $y$ trong $G$.

Các bộ test liên tiếp được ngăn cách bằng các dòng trống để dễ đọc.

Dữ liệu ra

Với mỗi bộ test, in số cạnh nhỏ nhất có thể của $G'$ trên một dòng mới.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

4
5

Ghi chú

Trong bộ test đầu tiên, Elsie có thể xây dựng $G'$ bằng cách bắt đầu từ $G$ và loại bỏ $(2,5)$. Hoặc cô ấy có thể xây dựng một đồ thị với các cạnh sau, vì cô ấy không bị giới hạn chỉ được loại bỏ cạnh của $G$:

1 2
1 4
4 3
4 5

Elsie chắc chắn không thể dùng ít hơn $N-1$ cạnh vì $G'$ cũng phải liên thông.

Dữ liệu vào 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

Dữ liệu ra 2

10
11
15
18
22
26
31

Ghi chú

Trong mỗi bộ test này, Elsie không thể làm tốt hơn Bessie.

Tác giả bài toán: Benjamin Qi