لإدارة الرعي بشكل أفضل، أنشأ Farmer John طرقًا أحادية الاتجاه في مزرعته. فيها $N$ حقل مرقمة $1..N$، ويربط كل طريق حقلين. طريق من $X$ إلى $Y$ يسمح بالذهاب من $X$ إلى $Y$ لا بالعكس.

تحب Bessie أكل العشب في أكبر عدد ممكن من الحقول. تبدأ صباحًا في الحقل $1$، تزور تسلسلًا من الحقول ثم تعود إلى $1$ مساءً. تعظم عدد الحقول المختلفة، لأنها تأكل عشب كل حقل مرة واحدة ولو زارته عدة مرات.

لا تحب قيد الاتجاه لأنه يقلل الزيارات. كم تستطيع الأكل إن خالفت القاعدة وسلكت طريقًا واحدًا على الأكثر عكس اتجاهه؟ احسب أكبر عدد من الحقول المختلفة لمسار يبدأ وينتهي في $1$ مع عبور عكسي واحد على الأكثر. يجوز العبور العكسي مرة واحدة فقط في الرحلة كلها، حتى الطريق نفسه لا يجوز عبوره عكسيًا مرتين.

الإدخال

يحتوي السطر الأول على عدد الحقول $N$ والطرق $M$ ($1 \leq N, M \leq 100,000$).

تحدد الأسطر $M$ التالية رقمين مختلفين $X$ و$Y$ لطريق من $X$ إلى $Y$. لا يتكرر أي طريق.

الإخراج

اطبع في سطر أكبر عدد من الحقول المختلفة لمسار من $1$ إلى $1$ مع عبور عكسي واحد على الأكثر.

أمثلة

الإدخال 1

7 10
1 2
3 1
2 5
2 4
3 7
3 5
3 6
6 5
7 2
4 7

الإخراج 1

6

ملاحظة

رسم ASCII للمثال:

v---3-->6
7   |\  |
^\  v \ |
| \ 1  \|
|  \|   v
|   v   5
4<--2---^

يمكنها زيارة $1,2,4,7,2,5,3,1$ بالعبور العكسي للطريق بين $5$ و$3$. عند $3$ لا يمكنها الوصول إلى $6$ دون عبور عكسي آخر.

مؤلف المسألة: Mark Gordon، 2015