Bessie tem um grafo $G$ conexo e não direcionado, com $N$ vértices numerados de $1\ldots N$ e $M$ arestas ($2\le N\le 10^5, N-1\le M\le \frac{N^2+N}{2}$). $G$ pode conter laços (arestas que ligam um vértice a si mesmo), mas não arestas paralelas (várias arestas ligando os mesmos extremos).

Seja $f_G(a,b)$ uma função booleana que vale verdadeiro se existe um caminho do vértice $1$ ao vértice $a$ que percorre exatamente $b$ arestas, para cada $1\le a\le N$ e $0\le b$, e falso caso contrário. Se uma aresta for percorrida várias vezes, ela será contada esse mesmo número de vezes.

Elsie quer copiar Bessie. Em particular, ela quer construir um grafo não direcionado $G'$ tal que $f_{G'}(a,b)=f_G(a,b)$ para todos os valores de $a$ e $b$.

Elsie quer fazer o mínimo possível de trabalho, portanto deseja construir o menor grafo possível. Assim, sua tarefa é calcular o menor número possível de arestas em $G'$.

Cada entrada contém $T$ ($1\le T\le 5\cdot 10^4$) casos de teste que devem ser resolvidos independentemente. É garantido que a soma de $N$ em todos os casos de teste não excede $10^5$, e a soma de $M$ em todos os casos de teste não excede $2\cdot 10^5$.

Entrada

A primeira linha da entrada contém $T$, o número de casos de teste.

A primeira linha de cada caso de teste contém dois inteiros $N$ e $M$.

Cada uma das próximas $M$ linhas de cada caso de teste contém dois inteiros $x$ e $y$ ($1\le x\le y\le N$), indicando que existe uma aresta entre $x$ e $y$ em $G$.

Casos de teste consecutivos são separados por linhas em branco para facilitar a leitura.

Saída

Para cada caso de teste, imprima o menor número possível de arestas em $G'$ em uma nova linha.

Exemplos

Entrada 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

Saída 1

4
5

Nota

No primeiro caso de teste, Elsie pode construir $G'$ começando com $G$ e removendo $(2,5)$. Ou ela pode construir um grafo com as seguintes arestas, pois não está limitada a apenas remover arestas de $G$:

1 2
1 4
4 3
4 5

Elsie certamente não pode obter um resultado menor que $N-1$, pois $G'$ também deve ser conexo.

Entrada 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

Saída 2

10
11
15
18
22
26
31

Nota

Em cada um desses casos de teste, Elsie não pode obter um resultado melhor que o de Bessie.

Autor do problema: Benjamin Qi