该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

憨憨最近正在致力于骑行运动，正好钱塘江边有很多骑行道可以供他骑行。

假设江边一共有 $N$ 个路口，编号为 $1$ 至 $N$，并且有 $M$ 条道路连接着。他准备从其中一个路口出发，并且只往东面骑行，直到骑行到路口 $i$ 停止。

所以他就需要选择最先到达的路口，并制定一条路线以路口 $i$ 为终点，使得线路上除了第一个路口，每个路口都在路线前一个路口东面，并且满足这个前提下还希望经过的路口尽量多。

现在，你只知道每一条道路所连接的两个路口的相对位置关系，但并不知道所有路口具体的位置。现在对于所有的 $i$，都需要你为憨憨制定一条路线，并求出以路口 $i$ 为终点最多能够经过多少个路口。

输入格式

第一行为两个正整数 $N,M$。

接下来 $M$ 行，每行两个正整数 $x,y$，表示了有一条连接路口 $x$ 与路口 $y$ 的道路，保证了路口 $x$ 在路口 $y$ 西面。

输出格式

$N$ 行，第 $i$ 行包含一个正整数，表示以第 $i$ 个路口为终点最多能经过多少个路口。

5 6
1 2
1 3
2 3
2 4
3 4
2 5

1
2
3
4
3

数据范围

• 对于 $20\%$ 的数据，$1≤N≤100$；
• 对于 $60\%$ 的数据，$1≤N≤1000$；
• 对于 $100\%$ 的数据，$1≤N≤100000，1≤M≤200000$。