Problem Description

Day 1 Problem B.

This problem is translated from EGOI2023 ppp.

Problem Description

There are $N$ players numbered from $0$ to $N-1$ participating in a $M$-day padel tournament. Exactly one match is played each day. A total of $M$ medals are awarded throughout the tournament, with one new medal awarded per match. On the $i$-th day ($0 \le i \le M-1$), two players numbered $x_i$ and $y_i$ compete. The following events occur during the match:

• Player $x_i$ defeats player $y_i$.
• A new medal is awarded to the winner $x_i$.
• All existing medals of the loser are transferred to the winner.

The awards ceremony takes place on the $M$-th day (the day after the last match). At the ceremony, all medals are collected and awarded to the player who held the medal for the longest time. Specifically, on the $M$-th day, medal $i$ is awarded to the player who held medal $i$ for the most nights (not necessarily consecutively). If two or more players held a medal for the same number of nights, the medal is awarded to the player with the smallest number.

Your task is to determine how many medals each player is awarded at the ceremony.

Input Format

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

The next $M$ lines each contain two integers $x_i$ and $y_i$, indicating that in the $i$-th match, player $x_i$ defeats player $y_i$.

Output Format

A single line containing $N$ integers, where the $k$-th integer represents the number of medals awarded to the $k$-th player at the ceremony.

Sample Input and Output

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

Notes

Sample 1 Explanation

The diagram below shows the medal ownership during the tournament for Sample 1. When player 1 is defeated on the third day, all her medals are transferred to player 2.

Sample 2 Explanation

As shown in the diagram below.

At the 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, and 2.

Data Range

For all data, $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 the $i$-th match participates in the $(i+1)$-th match, depends on Subtask 1.
• Subtask 4 (20 points): At the $i$-th match, $x_i$ has at least as many medals as $y_i$.
• Subtask 5 (22 points): Once a player is defeated, she never participates again.
• Subtask 6 (15 points): No special restrictions, depends on Subtasks 2, 3, 4, and 5.

见题面 Input 部分

见题面 Output 部分