题目描述

有 $N$ 座城市和 $M$ 条道路。输入的 $x\to y$ 表示城市 $x$ 在城市 $y$ 西侧，游客只能沿道路一直向东走。对每个城市 $i$，求以它为终点时最多能游览的城市数量；可以自行选择起点，起点也计入数量。

输入格式

第一行两个整数 $N,M$。接下来 $M$ 行，每行两个整数 $x,y$，表示一条从 $x$ 向东通往 $y$ 的道路。

输出格式

输出 $N$ 行，第 $i$ 行是以城市 $i$ 为终点的最多游览城市数。

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

1
1
2
2
3
4

数据范围

$1\le N\le 10^5$，$1\le M\le 2\times 10^5$。道路指向东侧，因此不会形成有向环。

提示

按拓扑顺序处理城市。以当前点为终点的最优方案，可以沿一条出边延长到后继城市。