ใน 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