Jealous Teachers

The Korea Science Academy of KAIST (KSA) has $N$ teachers and $N$ students. Because tomorrow is Teacher's Day in Korea, each student bought $N$ flowers. However, one student quit, so only $N-1$ students remain at the school.

The teachers are very jealous, so they give an F grade to a student who gives them fewer flowers than the other students do. Therefore, every teacher must receive exactly $N-1$ flowers. A student can give flowers only to teachers who have taught that student, and you are given which students learned from which teachers.

Seunghyun is a student at KSA, and he needs your help organizing this event.

The first line contains two integers $N$ and $M$, the number of teachers and the number of (student, teacher) pairs where the student learned from the teacher.

The next $M$ lines describe the relations. The $j$-th line contains two integers $s_j$ and $t_j$, meaning that the $s_j$-th student can give flowers to the $t_j$-th teacher. All pairs are distinct.

If it is impossible to give all teachers the same number of flowers ($N-1$ flowers), print $-1$ on the first line.

Otherwise, output $M$ lines. The $j$-th line must contain a single integer, the number of flowers that the $s_j$-th student gave to the $t_j$-th teacher.

If there are multiple possible answers, you may output any of them.

• $2 \le N \le 100\,000$
• $1 \le M \le 200\,000$
• $1 \le s_j \le N-1$ ($1 \le j \le N$)
• $1 \le t_j \le N$ ($1 \le i \le N$)