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

Với mỗi \(1\le a\le N\) và \(0\le b\), đặt \(f_G(a,b)\) là hàm Boolean bằng đúng nếu tồn tại một đường đi từ đỉnh \(1\) đến đỉnh \(a\) đi qua đúng \(b\) cạnh, và bằng sai nếu không tồn tại. Nếu một cạnh được đi qua nhiều lần, mỗi lần đều được tính vào số cạnh.

Elsie muốn sao chép Bessie. Cụ thể, cô 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 nên cần xây đồ thị nhỏ nhất có thể. Hãy tính số cạnh nhỏ nhất có thể có trong \(G'\).

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

Dữ liệu vào

Dòng đầu tiên chứa \(T\), số bộ test.

Dòng đầu của mỗi bộ test chứa \(N\) và \(M\). Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(x\) và \(y\) (\(1\le x\le y\le N\)), biểu thị một cạnh giữa \(x\) và \(y\) trong \(G\).

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

Dữ liệu ra

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

Phân nhóm

• Mọi bộ test trong input 3 thỏa mãn \(N\le5\).
• Mọi bộ test trong các input 4-5 thỏa mãn \(M=N\).
• Với mọi bộ test trong các input 6-9, nếu không phải \(f_G(x,b)=f_G(y,b)\) với mọi \(b\), thì tồn tại \(b\) sao cho \(f_G(x,b)\) đúng và \(f_G(y,b)\) sai.
• Mọi bộ test trong các input 10-15 thỏa mãn \(N\le10^2\).
• Các bộ test trong các input 16-20 không có ràng buộc bổ sung.

Ví dụ

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

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

Giải thích ví dụ 1. Trong bộ test đầu tiên, Elsie có thể dựng \(G'\) bằng cách bắt đầu từ \(G\) rồi xóa cạnh \((2,5)\). Cô cũng có thể dựng đồ thị gồm các cạnh sau vì không bị giới hạn ở việc chỉ xóa cạnh khỏi \(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.

Giải thích ví dụ 2. Trong mỗi bộ test này, Elsie không thể tạo đồ thị có ít cạnh hơn Bessie.

Nguồn

USACO 2021 February Contest, Platinum - Minimizing Edges: https://usaco.org/index.php?page=viewproblem2&cpid=1117

Tác giả: Benjamin Qi.