시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 (추가 시간 없음) | 1024 MB | 65 | 23 | 19 | 42.222% |
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.
This subtask has an additional constraint:
This subtask has no additional constraints.
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 0 5 5 1 2 4 3 0 3 1 5
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
-1
University > KAIST > 2019 KAIST RUN Spring Contest H번
Contest > Open Cup > 2018/2019 Season > Stage 19: Grand Prix of Daejeon J번