P1137 旅行计划

题目描述

给出有 $N$ 个点 $M$ 条有向边 的有向无环图。求以每个点 $i$ 为终点的最长路径所经过的点数。

输入格式

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

接下来 $M$ 行，每行两个正整数 $x, y$，表示了有一条从点 $x$ 与点 $y$ 的有向边。

输出格式

$N$ 行，第 $i$ 行包含一个正整数，表示以第 $i$ 个点为终点的最长路径所经过的点数。

输入输出样例 #1

输入 #1

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

输出 #1

1
2
3
4
3

说明/提示

均选择从城市 $1$ 出发可以得到以上答案。

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