← 返回题目列表

Codeforces · 459/E

E. Pashmak 和图表

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

Pashmak 的作业是一道关于图表的问题。尽管他总是尽力把作业做完整,但他无法解决这个问题。如你所知,他在图论方面确实很弱;所以尝试帮助他解决问题。

给定一个具有 n 个顶点和 m 个边的加权有向图。您需要找到一条具有最大边数的路径(可能不是简单的),使得边的权重沿着路径增加。换句话说,路径的每条边的权重必须严格大于路径中前一条边的权重。

帮助Pashmak,打印所需路径中的边数。

输入

第一行包含两个整数 n、m (2 ≤ n ≤ 3·105; 1 ≤ m ≤ min(n·(n - 1), 3·105))。然后是 m 行。第 i 行包含三个空格分隔的整数:ui, vi, wi (1 ≤ ui, vi ≤ n; 1 ≤ wi ≤ 105),这表示从顶点 ui 到顶点 vi 存在一条权重为 wi 的有向边。

保证图不包含自环和重边。

输出

打印一个整数——问题的答案。

示例

输入 #1

3 3
1 2 1
2 3 1
3 1 1

输出 #1

1

输入 #2

3 3
1 2 1
2 3 2
3 1 3

输出 #2

3

输入 #3

6 7
1 2 1
3 2 5
2 4 2
2 5 2
2 6 9
5 4 3
4 3 4

输出 #3

6

注意

在第一个示例中,最大轨迹可以是以下轨迹中的任何一个:$$1 \rightarrow 2, 2 \rightarrow 3, 3 \rightarrow 1$$。

在第二个样本中,最大轨迹为 $$1 \rightarrow 2 \rightarrow 3 \rightarrow 1$$。

在第三个样本中,最大轨迹为 $$1 \rightarrow 2 \rightarrow 5 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 6$$。