Background

Day 1 Problem B.

Translated from EGOI2023 ppp。

Problem Description

There are $N$ players numbered from $0$ to $N-1$ participating in a $M$-day padel tournament. Each day, exactly one match is played. In total, $M$ medals are awarded during the tournament, and each match awards one new medal. In the match on day $i$ ($0\le i\le M-1$), two players with numbers $x_i$ and $y_i$ play. The following happens:

• Player $x_i$ defeats player $y_i$.
• A new medal is given to the winner $x_i$.
• All medals currently owned by the loser are given to the winner.

On day $M$ (the day after the last match), an award ceremony is held. At the ceremony, all medals are collected and awarded to the player who has held that medal for the most nights. Specifically, on day $M$, medal $i$ is awarded to the player who has held medal $i$ for the largest number of nights (not necessarily continuously). If two or more players have held a medal for the same number of nights, the medal is awarded to the one with the smallest index.

Your task is to compute, at the award ceremony, how many medals each player is awarded.

Input Format

The first line contains two integers $N,M$, representing the number of players and the number of matches.

The next $M$ lines each contain two integers $x_i,y_i$, meaning that in the match on day $i$, player $x_i$ defeats player $y_i$.

Output Format

Output one line with $N$ integers. The $k$-th integer is the number of medals awarded to player $k$ at the award ceremony.

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

Hint

Explanation of Sample 1

The figure below shows who owns each medal during the tournament in Sample 1. When player $1$ is defeated on the third day, all of her medals are given to player $2$.

Explanation of Sample 2

As shown in the figure below.

At the award ceremony, player $0$ is awarded medals $5$ and $6$, player $1$ is awarded medals $3$ and $4$, and player $2$ is awarded medals $0,1,2$.

Constraints

For all testdata, $2\le N\le 2\times 10^5$, $1\le M\le 2\times 10^5$, $0\le x_i,y_i\le N-1$ and $x_i\ne y_i$.

• Subtask 1 ($12$ points): $N=2$.
• Subtask 2 ($16$ points): $N,M\le 2\times 10^3$.
• Subtask 3 ($15$ points): The winner of match $i$ participates in match $i+1$, depends on Subtask 1.
• Subtask 4 ($20$ points): In match $i$, $x_i$ has at least as many medals as $y_i$.
• Subtask 5 ($22$ points): Once a player is defeated, she will never play again.
• Subtask 6 ($15$ points): No additional constraints, depends on Subtasks 2, 3, 4, and 5.

Translated by ChatGPT 5