题目描述

小霖打算去一个陌生的国度深度游。这个国度里有 $N$ 座城镇，编号为 $1$ 至 $N$，城镇之间有 $M$ 条公路相连。小霖给自己立了个规矩：从某座城镇出发后一路只向东走，最终在某座城镇 $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

提示

样例中全部从城镇 $1$ 出发即可得到对应答案。

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