← 返回题目列表

AtCoder · dp_g

G. 最长路径

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

有一个有向图 G 与 N 顶点和 M 边缘。 顶点已编号 1, 2, \ldots, N,并且对于每个 i (1 \leq i \leq M), i第一条有向边从顶点出发 x_i to y_i. G 不包含有向循环.

找出最长有向路径的长度 G。 这里,有向路径的长度是其中的边数。

约束

  • 输入中的所有值都是整数。
  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq x_i, y_i \leq N
  • 所有对 (x_i, y_i) 是不同的。
  • G 不包含有向循环.

输入

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

N M
x_1 y_1
x_2 y_2
:
x_M y_M

输出

打印最长有向路径的长度 G.


示例输入 1

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

示例输出 1

3

下图中红色有向路径最长:


示例输入 2

6 3
2 3
4 5
5 6

示例输出 2

2

下图中红色有向路径最长:


示例输入 3

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

示例输出 3

3

下图中的红色有向路径是最长的路径之一: