Bessie possède un graphe $G$ connexe et non orienté, avec $N$ sommets numérotés $1\ldots N$ et $M$ arêtes ($2\le N\le 10^5, N-1\le M\le \frac{N^2+N}{2}$). $G$ peut contenir des boucles (des arêtes reliant un sommet à lui-même), mais aucune arête parallèle (plusieurs arêtes reliant les mêmes extrémités).

Pour chaque $1\le a\le N$ et $0\le b$, soit $f_G(a,b)$ une fonction booléenne qui vaut vrai s'il existe un chemin du sommet $1$ au sommet $a$ parcourant exactement $b$ arêtes, et faux sinon. Si une arête est parcourue plusieurs fois, elle est comptée autant de fois.

Elsie veut imiter Bessie. Plus précisément, elle veut construire un graphe non orienté $G'$ tel que $f_{G'}(a,b)=f_G(a,b)$ pour tous $a$ et $b$.

Elsie veut travailler le moins possible et souhaite donc construire le plus petit graphe possible. Votre tâche est ainsi de calculer le nombre minimal possible d'arêtes dans $G'$.

Chaque entrée contient $T$ ($1\le T\le 5\cdot 10^4$) cas de test à résoudre indépendamment. Il est garanti que la somme des $N$ sur tous les cas de test ne dépasse pas $10^5$, et que la somme des $M$ sur tous les cas de test ne dépasse pas $2\cdot 10^5$.

Entrée

La première ligne de l'entrée contient $T$, le nombre de cas de test.

La première ligne de chaque cas de test contient deux entiers $N$ et $M$.

Les $M$ lignes suivantes de chaque cas de test contiennent chacune deux entiers $x$ et $y$ ($1\le x\le y\le N$), indiquant qu'il existe une arête entre $x$ et $y$ dans $G$.

Les cas de test consécutifs sont séparés par des lignes vides pour faciliter la lecture.

Sortie

Pour chaque cas de test, affichez sur une nouvelle ligne le nombre minimal possible d'arêtes dans $G'$.

Exemples

Entrée 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

Sortie 1

4
5

Remarque

Dans le premier cas de test, Elsie peut construire $G'$ en partant de $G$ et en supprimant $(2,5)$. Elle pourrait aussi construire un graphe avec les arêtes suivantes, puisqu'elle n'est pas limitée à supprimer des arêtes de $G$ :

1 2
1 4
4 3
4 5

Elsie ne peut certainement pas faire mieux que $N-1$, car $G'$ doit lui aussi être connexe.

Entrée 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

Sortie 2

10
11
15
18
22
26
31

Remarque

Dans chacun de ces cas de test, Elsie ne peut pas faire mieux que Bessie.

Auteur du problème : Benjamin Qi