레이팅 미적용There are \(N\) participants numbered \(0\) to \(N-1\) competing in a padel tournament held over \(M\) days. Exactly one match is held each day. There are \(M\) medals handed out in the tournament, a new one for each match. In the match on day \(i\) \((0 \le i \le M-1)\), the two participants numbered \(x_i\) and \(y_i\) are participating. The following happens in the match:
- Participant \(x_i\) beats participant \(y_i\).
- A new medal is given to the winner \(x_i\).
- All of the loser's current medals are given to the winner.
On day \(M\) (the day after the last match) the prize ceremony is held. At the ceremony, all medals are collected and then each medal is given to the participant that held that medal the longest. Formally, medal \(i\) is given to the participant who held medal \(i\) for the most nights (not necessarily in a row), as of day \(M\). If two or more participants have held a medal for the same number of nights, the medal is given to the participant with the smallest index among them.
Your goal is to determine how many medals each participant is awarded at the prize ceremony.
(An illustrative figure from the official statement is omitted here.)
- \(2 \leq N \leq 200\,000\).
- \(1 \leq M \leq 200\,000\).
- \(0 \le x_i, y_i \le N-1\) and \(x_i \neq y_i\) (for all \(0\le i \le M-1\)).
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
Group | Score | Limits 1 | 12 | \(N = 2\) 2 | 16 | \(N, M \le 2000\) 3 | 15 | The winner of the \(i\)th match participates in the \((i + 1)\)th match, for every \(i\) such that \(0 \le i \le M-2\). 4 | 20 | At the time of the \(i\)th match, \(x_i\) has at least as many medals as \(y_i\), for every \(i\) such that \(0 \le i \le M-1\). 5 | 22 | Once a participant loses, they are never in a match again. 6 | 15 | No additional constraints
The first line of input contains the integers \(N\) and \(M\), the number of participants and number of matches.
Then \(M\) lines follow. The \(i\)th of these lines contains two integers \(x_i\) and \(y_i\), the participants competing on day \(i\), where participant \(x_i\) beats participant \(y_i\).
On the single line of output print \(N\) integers, the \(k\)th number denoting the number of medals that participant \(k\) has after the prize ceremony.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 12점 | None |
Subtask 2 | 16점 | None |
Subtask 3 | 15점 | None |
Subtask 4 | 20점 | None |
Subtask 5 | 22점 | None |
Subtask 6 | 15점 | None |
3 4
0 1
2 1
1 0
2 1
1 1 2
3 7
0 1
0 2
2 0
0 1
1 0
2 0
0 2
2 2 3
6 10
2 5
3 0
4 2
0 1
4 3
2 4
0 3
0 2
5 2
5 0
5 0 1 1 1 2