Farmer John רוצה לחבר $N$ אסמים ($1 \le N \le 1{,}000$), ממוספרים $1..N$, ברשת סיבים אופטיים. הם במעגל סביב ברכה גדולה, ולכן אפשר לחבר רק שכנים; אסם $N$ שכן של 1.

לא חייבים לחבר הכול: רק זוגות פרות מסוימים רוצים לתקשר. הוא רוצה מעט חיבורים ככל האפשר, תוך מתן תקשורת לכל הזוגות דרך הרשת. לפי רשימת הזוגות מצאו מינימום קווים. כדי לתקשר מ־1 ל־3 יש לפרוס 1-2 ו־2-3.

קלט

• שורה $1$: השלמים $N$ ו־$P$, האחרון מספר זוגות התקשורת ($1 \le P \le 10{,}000$).

• שורות $2..P+1$: שני שלמים המציינים זוג אסמים שרוצה לתקשר. אין זוג חוזר.

פלט

שורה אחת עם שלם, מינימום החיבורים הישירים הדרוש.

דוגמאות

קלט 1

5 2
1 3
4 5

פלט 1

3

Note

מחברים את זוגות האסמים 1-2, 2-3 ו־4-5.

מקור: Reid Barton, 2001.