#AT7. Longest Path

Longest Path

[G] Longest Path(dp_g)

来源: AtCoder Educational DP Contest - Problem G 原题时限:2 秒 / 内存:1024 MB

题目描述

有 NN 个顶点(编号 1∼N1 \sim N)和 MM 条有向边的有向图。第 ii 条边从顶点 xix_i 指向顶点 yiy_i。

保证该图不含有向环。

求图中最长有向路径的长度(即路径上的边数)。

输入格式

输入由标准输入按以下格式给出:

N M
x_1 y_1
x_2 y_2
:
x_M y_M

输出格式

输出图中最长有向路径的长度。

数据范围

  • 输入中的所有值均为整数。
  • 2≤N≤1052 \le N \le 10^5
  • 1≤M≤1051 \le M \le 10^5
  • 1≤xi,yi≤N1 \le x_i, y_i \le N
  • 所有有序对 (xi,yi)(x_i, y_i) 互不相同。
  • 图 GG 中不含有向环。

样例 1

输入:

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

输出:

3

样例 2

输入:

6 3
2 3
4 5
5 6

输出:

2

样例 3

输入:

5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3

输出:

3