ל-Farmer John יש $N$ מרעים ($1 \leq N \leq 50,000$), שמספריהם $1...N$, המחוברים ב-$M$ דרכים דו-כיווניות ($1 \leq M \leq 100,000$). דרך $i$ מחברת $A_i$ ($1 \leq A_i \leq N$) ל-$B_i$ ($1 \leq B_i \leq N$), עם $A_i != B_i$. שתי דרכים עשויות לחבר אותו זוג.

Bessie מקשטת לכבוד יום הולדת FJ. רוצה בכל מרעה שלט גדול '$F$' או '$J$', אך כדי לא לבלבל אותו, מרעים המחוברים בדרך חייבים אותיות שונות.

החברה גובה על '$F$' יותר מעל '$J$', ולכן היא ממקסמת את מספר '$J$'. מצאו אותו או הדפיסו -1 אם אין סידור תקין.

קלט

• שורה 1: השלמים $N$, $M$.
• שורות $2..M+1$: השלמים $A_i$, $B_i$, המציינים דרך דו-כיוונית בין $A_i$ ל-$B_i$.

פלט

• שורה 1: שלם המציין את מספר שלטי '$J$' המרבי. אם אין פתרון תקין, הדפיסו -1.

דוגמאות

קלט 1

4 4
1 2
2 3
3 4
4 1

פלט 1

2

הערה

המרעים והדרכים יוצרים קודקודים וצלעות של ריבוע.

Bessie יכולה לבחור מרעים 1 ו-3 ל-'$J$', או לחלופין 2 ו-4.

מחבר הבעיה: Kalki Seksaria, 2014