כדי לנהל טוב יותר את המרעה, 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