European Girls' Olympiad in Informatics: 2023 Day 1 Problem 2

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:

1. Participant $x_i$ beats participant $y_i$.
2. A new medal is given to the winner $x_i$.
3. 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.

Input Specification

The first line of input contains the integers $N$ and $M$, the number of participants and the 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$.

Output Specification

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.

Constraints and Scoring

• $2\le N\le 200000$.
• $1\le M\le 200000$.
• $0\le x_i,y_i\le N-1$ and $x_i\ne 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.

Example

For the first sample test case, the following illustration shows who held which medals throughout the tournament. When participant 1 loses on the 3rd day, all her medals are given to participant 2.

The second sample can be seen below.

After the prize ceremony, participant 0 is given medals 5 and 6, participant 1 is given medals 3 and 4, and participant 2 is given medals 0, 1 and 2.

Sample Input 1

3 4
0 1
2 1
1 0
2 1

Sample Output 1

1 1 2

Sample Input 2

3 7
0 1
0 2
2 0
0 1
1 0
2 0
0 2

Sample Output 2

2 2 3

Sample Input 3

6 10
2 5
3 0
4 2
0 1
4 3
2 4
0 3
0 2
5 2
5 0

Sample Output 3

5 0 1 1 1 2

---