Padel Prize Pursuit

There are $N$ participants numbered $0$ to $N-1$ in a padel tournament that lasts $M$ days. Exactly one match is played each day. One medal is handed out per match, so there are $M$ medals in total. On day $i$ $(0 \le i \le M-1)$, participants $x_i$ and $y_i$ play. The match goes as follows:

1. Participant $x_i$ beats participant $y_i$.
2. A new medal goes to the winner $x_i$.
3. All of the loser's current medals go to the winner.

On day $M$, the day after the last match, the prize ceremony is held. At the ceremony, all medals are collected. Each medal then goes to the participant who held it for the most nights as of day $M$. The nights do not need to be consecutive. If two or more participants held a medal for the same number of nights, the medal goes to the one with the smallest index. Find how many medals each participant receives at the ceremony.

The first line contains the integers $N$ and $M$, the number of participants and the number of matches.

The next $M$ lines each contain two integers $x_i$ and $y_i$. Line $i$ gives the participants of the match on day $i$, where $x_i$ beats $y_i$.

Print $N$ integers on a single line. The $k$th integer is the number of medals participant $k$ has after the prize ceremony.

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

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 go to participant 2.

The second sample is shown below.

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