يوجد $N$ معلّمًا و$N$ طالبًا في Seoul Science High School. اشترى كل طالب $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