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 \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$

子任务