题目描述

题目译自 European Girls' Olympiad in Informatics 2023 Day1 T2. Padel Prize Pursuit

在一场为期 $M$ 天的帕德尔锦标赛中，有 $N$ 名参赛者，编号从 $0$ 到 $N-1$。每天恰好举行一场比赛。整个锦标赛共颁发 $M$ 枚奖牌，每场比赛颁发一枚新奖牌。

在第 $i$ $(0 \leq i \leq M-1)$ 天的比赛中，编号为 $x_i$ 和 $y_i$ 的两名参赛者对决。比赛按以下步骤进行：

1. 参赛者 $x_i$ 击败参赛者 $y_i$。
2. 胜者 $x_i$ 获得一枚新奖牌。
3. 败者当前持有的所有奖牌都转交给胜者。

在第 $M$ 天（最后一场比赛后的第二天），举行颁奖仪式。仪式上，所有奖牌被收集，然后每枚奖牌被颁发给持有该奖牌最久（以夜晚数计算，不必连续）的参赛者。形式上，奖牌 $i$ 颁发给截至第 $M$ 天持有奖牌 $i$ 夜晚数最多的参赛者。如果有多名参赛者持有奖牌的夜晚数相同，奖牌颁发给其中编号最小的参赛者。

你的目标是确定颁奖仪式后每名参赛者获得的奖牌数量。

输入格式

第一行包含两个整数 $N,M$，分别表示参赛者数量和比赛天数。

接下来的 $M$ 行，第 $i$ 行包含两个整数 $x_i, y_i$，表示第 $i$ 天比赛的两位参赛者，其中 $x_i$ 击败 $y_i$。

输出格式

输出一行，包含 $N$ 个整数，第 $k$ 个数字表示参赛者 $k$ 在颁奖仪式后获得的奖牌数量。

3 4
0 1
2 1
1 0
2 1

1 1 2

以下图示展示了锦标赛中奖牌的持有情况。参赛者 $1$ 在第 $3$ 天输掉比赛时，将所有奖牌转交给参赛者 $2$。

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

2 2 3

以下图示展示了锦标赛的奖牌流转情况。

在颁奖仪式后：

• 参赛者 $0$ 获得奖牌 $5$ 和 $6$，共 $2$ 枚。
• 参赛者 $1$ 获得奖牌 $3$ 和 $4$，共 $2$ 枚。
• 参赛者 $2$ 获得奖牌 $0, 1, 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

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 200000$
• $1 \leq M \leq 200000$
• $0 \leq x_i, y_i \leq N-1$ 且 $x_i \neq y_i$（对于所有 $0 \leq i \leq M-1$）

详细子任务附加限制及分值如下表所示。