ל-Bessie יש גרף קשיר ולא מכוון $G$ עם $N$ קודקודים הממוספרים $1\ldots N$ ו-$M$ קשתות ($2\le N\le 10^5, N-1\le M\le \frac{N^2+N}{2}$). הגרף $G$ עשוי להכיל לולאות עצמיות (קשתות מקודקוד לעצמו), אך אינו מכיל קשתות מקבילות (כמה קשתות המחברות את אותם קודקודי קצה).

תהי $f_G(a,b)$ פונקציה בוליאנית שערכה אמת אם קיים מסלול מקודקוד $1$ לקודקוד $a$ העובר בדיוק $b$ קשתות, לכל $1\le a\le N$ ו-$0\le b$, ושקר אחרת. אם עוברים בקשת כמה פעמים, היא נספרת כמספר הפעמים שעוברים בה.

Elsie רוצה לחקות את Bessie. בפרט, היא רוצה לבנות גרף לא מכוון $G'$ כך ש-$f_{G'}(a,b)=f_G(a,b)$ לכל $a$ ו-$b$.

Elsie רוצה לעבוד מעט ככל האפשר, ולכן היא רוצה לבנות גרף קטן ככל האפשר. לפיכך, עליכם לחשב את מספר הקשתות המינימלי האפשרי ב-$G'$.

כל קלט מכיל $T$ ($1\le T\le 5\cdot 10^4$) מקרי בדיקה שיש לפתור באופן בלתי תלוי. מובטח שסכום הערכים של $N$ בכל מקרי הבדיקה אינו עולה על $10^5$, וסכום הערכים של $M$ בכל מקרי הבדיקה אינו עולה על $2\cdot 10^5$.

קלט

השורה הראשונה של הקלט מכילה את $T$, מספר מקרי הבדיקה.

השורה הראשונה של כל מקרה בדיקה מכילה שני מספרים שלמים $N$ ו-$M$.

כל אחת מ-$M$ השורות הבאות של כל מקרה בדיקה מכילה שני מספרים שלמים $x$ ו-$y$ ($1\le x\le y\le N$), המציינים שקיימת קשת בין $x$ ל-$y$ ב-$G$.

מקרי בדיקה עוקבים מופרדים בשורות ריקות כדי להקל על הקריאה.

פלט

לכל מקרה בדיקה, הדפיסו בשורה נפרדת את מספר הקשתות המינימלי האפשרי ב-$G'$.

דוגמאות

קלט 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

פלט 1

4
5

הערה

במקרה הבדיקה הראשון, Elsie יכולה לבנות את $G'$ על ידי התחלה מ-$G$ והסרת $(2,5)$. לחלופין, היא יכולה לבנות גרף עם הקשתות הבאות, שכן היא אינה מוגבלת להסרת קשתות מ-$G$ בלבד:

1 2
1 4
4 3
4 5

Elsie בוודאי אינה יכולה להשיג פחות מ-$N-1$ קשתות, שכן גם $G'$ חייב להיות קשיר.

קלט 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

פלט 2

10
11
15
18
22
26
31

הערה

בכל אחד ממקרי הבדיקה האלה, Elsie אינה יכולה להשיג תוצאה טובה יותר מזו של Bessie.

מחבר הבעיה: Benjamin Qi