Bessie hat einen zusammenhängenden, ungerichteten Graphen $G$ mit $N$ Knoten, die mit $1\ldots N$ beschriftet sind, und $M$ Kanten ($2\le N\le 10^5, N-1\le M\le \frac{N^2+N}{2}$). $G$ darf Schleifen enthalten (Kanten von einem Knoten zu sich selbst), aber keine parallelen Kanten (mehrere Kanten mit denselben Endpunkten).

Sei $f_G(a,b)$ eine boolesche Funktion, die für jedes $1\le a\le N$ und $0\le b$ genau dann wahr ist, wenn es einen Weg von Knoten $1$ zu Knoten $a$ gibt, der genau $b$ Kanten durchläuft, und andernfalls falsch. Wird eine Kante mehrfach durchlaufen, wird sie entsprechend oft mitgezählt.

Elsie möchte Bessie nachahmen. Insbesondere möchte sie einen ungerichteten Graphen $G'$ konstruieren, für den $f_{G'}(a,b)=f_G(a,b)$ für alle $a$ und $b$ gilt.

Elsie möchte möglichst wenig Arbeit haben und deshalb einen möglichst kleinen Graphen konstruieren. Deine Aufgabe ist daher, die kleinstmögliche Anzahl von Kanten in $G'$ zu berechnen.

Jede Eingabe enthält $T$ ($1\le T\le 5\cdot 10^4$) Testfälle, die unabhängig voneinander gelöst werden sollen. Es ist garantiert, dass die Summe von $N$ über alle Testfälle $10^5$ nicht überschreitet und die Summe von $M$ über alle Testfälle $2\cdot 10^5$ nicht überschreitet.

Eingabe

Die erste Zeile der Eingabe enthält $T$, die Anzahl der Testfälle.

Die erste Zeile jedes Testfalls enthält zwei ganze Zahlen $N$ und $M$.

Die nächsten $M$ Zeilen jedes Testfalls enthalten jeweils zwei ganze Zahlen $x$ und $y$ ($1\le x\le y\le N$), die angeben, dass es in $G$ eine Kante zwischen $x$ und $y$ gibt.

Aufeinanderfolgende Testfälle sind zur besseren Lesbarkeit durch Leerzeilen getrennt.

Ausgabe

Gib für jeden Testfall die kleinstmögliche Anzahl von Kanten in $G'$ in einer neuen Zeile aus.

Beispiele

Eingabe 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

Ausgabe 1

4
5

Hinweis

Im ersten Testfall kann Elsie $G'$ konstruieren, indem sie von $G$ ausgeht und $(2,5)$ entfernt. Sie könnte auch einen Graphen mit den folgenden Kanten konstruieren, da sie nicht darauf beschränkt ist, nur Kanten aus $G$ zu entfernen:

1 2
1 4
4 3
4 5

Elsie kann auf keinen Fall weniger als $N-1$ Kanten erreichen, da auch $G'$ zusammenhängend sein muss.

Eingabe 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

Ausgabe 2

10
11
15
18
22
26
31

Hinweis

In jedem dieser Testfälle kann Elsie kein besseres Ergebnis als Bessie erzielen.

Autor der Aufgabe: Benjamin Qi