בבית הספר Seoul Science High School יש $N$ מורים ו-$N$ תלמידים. כל תלמיד קנה $N$ פרחים משום שמחר הוא יום המורה בקוריאה. אולם אחד התלמידים עזב את בית הספר, וכעת נותרו בו רק $N-1$ תלמידים.

המורים קנאים מאוד, ולכן יתנו לתלמיד ציון F אם יקבלו ממנו פחות פרחים מאשר המורים האחרים. לכן כל מורה צריך לקבל בדיוק $N-1$ פרחים. תלמיד יכול לתת פרחים רק למורים שלימדו אותו, וידוע לך אילו תלמידים למדו אצל אילו מורים.

Younghun הוא תלמיד בבית הספר Seoul Science High School, והוא זקוק לעזרתך בארגון האירוע הזה.

קלט

השורה הראשונה מכילה שני מספרים שלמים $N$ ו-$M$ ($2 \le N \le 100 000$, $1 \le M \le 200 000$), המתארים את מספר המורים ואת מספר הזוגות (תלמיד, מורה) שבהם התלמיד למד אצל המורה.

$M$ השורות הבאות מתארות את הקשרים: השורה ה-$j$ מכילה שני מספרים שלמים $s_j$, $t_j$ ($1 \le s_j \le N-1$, $1 \le t_j \le N$), המציינים שהתלמיד ה-$s_j$ יכול לתת פרחים למורה ה-$t_j$. מובטח שכל הזוגות שונים זה מזה.

פלט

אם אי אפשר לתת לכל המורים מספר זהה של פרחים ($N-1$ פרחים), הדפיסו בשורה הראשונה מספר יחיד $-1$.

אחרת, על התוכנית להדפיס $M$ שורות. בשורה ה-$j$ צריך להופיע מספר שלם יחיד המציין את מספר הפרחים שהתלמיד ה-$s_j$ נתן למורה ה-$t_j$.

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

דוגמאות

קלט 1

6 12
1 3
1 4
1 5
2 2
2 4
3 1
3 3
4 1
4 2
4 4
5 4
5 6

פלט 1

1
0
5
5
1
2
4
3
0
3
1
5

קלט 2

6 12
1 2
1 3
1 4
2 2
2 4
3 1
3 3
4 1
4 2
4 4
5 5
5 6

פלט 2

-1