Minimizing Edges

문제

Bessie has a connected, undirected graph $GG$ with $NN$ vertices labeled $1\dots N1\backslash ldots\; N$ and $MM$ edges ($2\le N\le {10}^5,N-1\le M\le \frac{N^2+N}{2}2\backslash le\; N\backslash le\; 10^5,\; N-1\backslash le\; M\backslash le\; \backslash frac\{N^2+N\}\{2\}$). $GG$ 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)f\_G(a,b)$ be a boolean function that evaluates to true if there exists a path from vertex $11$ to vertex $aa$ that traverses exactly $bb$ edges for each $1\le a\le N1\backslash le\; a\backslash le\; N$ and $0\le b0\backslash le\; 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^{\mathrm{\prime }}G\text{'}$ such that $f_{G^{\mathrm{\prime }}}(a,b)=f_G(a,b)f\_\{G\text{'}\}(a,b)=f\_G(a,b)$ for all $aa$ and $bb$.

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^{\mathrm{\prime }}G\text{'}$.

Each input contains $TT$ ($1\le T\le 5\cdot {10}^{4}1\backslash le\; T\backslash le\; 5\backslash cdot\; 10^4$) test cases that should be solved independently. It is guaranteed that the sum of $NN$ over all test cases does not exceed ${10}^{5}10^5$, and the sum of $MM$ over all test cases does not exceed $2\cdot {10}^{5}2\backslash cdot\; 10^5$.

입력

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

The first line of each test case contains two integers $NN$ and $MM$.

The next $MM$ lines of each test case each contain two integers $xx$ and $yy$ ($1\le x\le y\le N1\backslash le\; x\backslash le\; y\backslash le\; N$), denoting that there exists an edge between $xx$ and $yy$ in $GG$.

Consecutive test cases are separated by newlines for readability.

출력

For each test case, the minimum possible number of edges in $G^{\mathrm{\prime }}G\text{'}$ on a new line.

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