لدى 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