题目背景

Day 1 Problem B.

题面译自 EGOI2023 ppp。

题目描述

有 $N$ 个编号为 $0$ 到 $N-1$ 的选手参加一场 $M$ 天的笼式网球锦标赛。每天恰好进行一次比赛。在锦标赛中共颁发 $M$ 块奖牌，每场比赛颁发一块新奖牌。在第 $i$ 天的比赛中（$0\le i\le M-1$），两名编号分别为 $x_i$ 和 $y_i$ 的选手参加。比赛中发生如下事件：

• 选手 $x_i$ 打败选手 $y_i$。
• 一个新的奖牌授予给获胜者 $x_i$。
• 失败者所有现有的奖牌都授予给获胜者。

在第 $M$ 天（最后一场比赛结束后一天）举行颁奖典礼。在颁奖典礼上，所有奖牌被收集起来，并授予给持有该奖牌时间最长的选手。具体地，在第 $M$ 天，奖牌 $i$ 授予给持有奖牌 $i$ 最多个晚上的选手（不必须连续持有）。如果两个或更多选手持有一个奖牌同样多晚上，奖牌授予给其中编号最小的选手。

你的任务是求出颁奖典礼中，每位选手被授予多少奖牌。

输入格式

第一行两个整数 $N,M$，表示选手数和比赛数。

接下来 $M$ 行，每行两个整数 $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

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

提示

样例 $1$ 解释

下图展示了样例 $1$ 中锦标赛期间奖牌的归属。当选手 $1$ 在第三天被打败时，她的所有奖牌都被授予给选手 $2$。

---

样例 $2$ 解释

如下图。

在颁奖典礼中，选手 $0$ 被授予奖牌 $5$ 和 $6$，选手 $1$ 被授予奖牌 $3$ 和 $4$，选手 $2$ 被授予奖牌 $0,1,2$。

---

数据范围

对于全部数据，$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$ 且 $x_i\ne y_i$。

• 子任务一（$12$ 分）：$N=2$。
• 子任务二（$16$ 分）：$N,M\le 2\times 10^3$。
• 子任务三（$15$ 分）：第 $i$ 场比赛的获胜者参加了第 $i+1$ 场比赛，依赖子任务一。
• 子任务四（$20$ 分）：在第 $i$ 场比赛时，$x_i$ 有至少和 $y_i$ 一样多的奖牌。
• 子任务五（$22$ 分）：一旦一名选手被打败，她永远不会再次参赛。
• 子任务六（$15$ 分）：无特殊限制，依赖子任务二、三、四、五。