There are $N$ teachers and $N$ students in the Seoul Science High School. Each student bought $N$ flowers because tomorrow is a teacher's day in Korea. However, one of the students quit, and now only $N-1$ students remain in the school.

Teachers are very jealous, so they will give an F grade to students when they receive fewer flowers from that student than others. Therefore, every teacher should receive exactly $N-1$ flowers. A student can only give flowers to teachers who have taught him or her, and you know which students have learned from which teachers.

Younghun is the student of Seoul Science High School, and he needs your help in organizing this event.

Input

The first line contains two integers $N$ and $M$ ($2 \le N \le 100 000$, $1 \le M \le 200 000$) describing the number of teachers and the number of (student, teacher) pairs where the student learned from the teacher.

In the next $M$ lines describe the relations: $j$-th line contains two integers $s_j$, $t_j$ ($1 \le s_j \le N-1$, $1 \le t_j \le N$) indicating that $s_j$-th student can give flowers to the $t_j$-th teacher. It is guaranteed that all pairs are different.

Output

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

Otherwise, your program should output $M$ lines. In $j$-th line, there should be a single integer denoting the number of flowers which $s_j$-th student gave to $t_j$-th teacher.

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

Examples

Input 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

Output 1

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

Input 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

Output 2

-1