גידול הפרות יוצר עומס בשבילים לרפת. Farmer John חוקר צווארי בקבוק להקל ״פקקים״ בחליבה.

$M$ ($1 \le M \le 50,000$) שבילים חד-כיווניים מחברים שניים שונים מבין $N$ ($1 \le N \le 5,000$) צמתים $1..N$, רפת ב-$N$. תמיד למספר גדול יותר, אין מעגלים וכולם לרפת. כמה שבילים לזוג אפשריים.

בשעת שיא הולכות מאזורי המרעה לרפת: בדיוק צמתים בלי שבילים נכנסים. ״מסלול״ הוא רצף שבילים מכאן לרפת.

מצאו מספר מסלולים אפשריים מרבי המכילים שביל נתון אחד למציאת העמוס. התשובה נכנסת לשלם עם סימן 32 סיביות.

קלט

שורה 1: שלמים $N$, $M$ ברווח.

שורות $2..M+1$: שני צמתים ברווח.

פלט

שורה 1: מספר מסלולים מרבי דרך שביל אחד.

דוגמאות

קלט 1

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

פלט 1

4

הערה

ארבעה מסלולים אפשריים לרפת:

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

מקור: USACO מרץ 2007.