시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB56181438.889%

문제

There are $N$ teachers and $N$ students in the Korea Science Academy of KAIST (KSA). 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.

Seunghyun is the student of KSA, and he needs your help in organizing this event.

입력

The first line contains two integers $N$ and $M$ 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$  indicating that $s_j$-th student can give flowers to the $t_j$-th teacher. It is guaranteed that all pairs are different.

출력

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.

제한

  • $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$)

서브태스크 1 (32점)

This subtask has an additional constraint:

  • $N \le 100$

서브태스크 2 (68점)

This subtask has no additional constraints.

예제 입력 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

채점 및 기타 정보

  • 예제는 채점하지 않는다.