لدى Bobo رسم بياني غير موجه ومتصل $G$ يحتوي على $n$ رؤوس و$m$ حواف، وقد رُقمت رؤوسه بالأعداد $1,2,\ldots,n$.

يختار Bobo مجموعة جزئية غير فارغة من الحواف بحيث يبقى الرسم البياني المكوّن من الحواف المختارة متصلًا. ويريد معرفة عدد هذه المجموعات الجزئية بترديد $2$.

لاحظ أن الرسم البياني يكون متصلًا إذا وُجد، لأي رأسين $a$ و$b$، مسار يصل بينهما.

الإدخال

يحتوي الإدخال على صفر أو أكثر من حالات الاختبار، وينتهي بنهاية الملف. لكل حالة اختبار:

يحتوي السطر الأول على عددين صحيحين $n$ و$m$ ($2 \le n \le 2 \cdot 10^5$، $1 \le m \le 2 \cdot 10^5$).

يحتوي السطر رقم $i$ من الأسطر الـ$m$ التالية على عددين صحيحين $a_i$ و$b_i$ يحددان حافة بين الرأسين $a_i$ و$b_i$.

يُضمن أن مجموع جميع قيم $m$ لا يتجاوز $2 \cdot 10^5$، وأن جميع الرسوم البيانية المعطاة متصلة.

الإخراج

لكل حالة اختبار، اطبع عددًا صحيحًا يمثل الباقي بترديد $2$.

أمثلة

الإدخال 1

2 1
1 2
3 2
1 2
2 3
3 3
1 2
2 3
3 1

الإخراج 1

1
1
0