페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5776

Minimizing Edges 1초 512MB

문제

Bessie has a connected, undirected graph Gwith N vertices labeled 1…N and Medges (2≤N≤105,N−1≤M≤(N^2+N)/2). G may contain self-loops (edges from nodes back to themselves), but no parallel edges (multiple edges connecting the same endpoints).

Let f_G(a,b) be a boolean function that evaluates to true if there exists a path from vertex 1 to vertex a that traverses exactly b edges for each 1≤a≤N and 0≤b, and false otherwise. If an edge is traversed multiple times, it is included that many times in the count.

Elsie wants to copy Bessie. In particular, she wants to construct an undirected graph G′ such that f_G′(a,b)=f_G(a,b)

for all a and b.

Elsie wants to do the least possible amount of work, so she wants to construct the smallest possible graph. Therefore, your job is to compute the minimum possible number of edges in G′.

Each input contains T(1≤T≤5⋅10^4) test cases that should be solved independently. It is guaranteed that the sum of Nover all test cases does not exceed 10^5, and the sum of Mover all test cases does not exceed 2⋅10^5.


입력

The first line of the input contains T, the number of test cases.

The first line of each test case contains two integers Nand M.

The next M lines of each test case each contain two integers x and y (1≤x≤y≤N), denoting that there exists an edge between x and y in G.

Consecutive test cases are separated by newlines for readability.


출력

For each test case, the minimum possible number of edges in G′ on a new line


예제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
출력
4
5

In the first test case, Elsie can construct G′ by starting with G and removing (2,5). Or she could construct a graph with the following edges, since she isn't restricted to just removing edges from G:

1 2

1 4

4 3

4 5

Elsie definitely cannot do better than N−1 since G′ must also be connected.


예제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
출력
10
11
15
18
22
26
31

In each of these test cases, Elsie cannot do better than Bessie.


출처

USACO 2021 Febuary Platinum

역링크 공식 문제집만