← 返回题目列表

Codeforces · 960/F

F. 步道

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

给你一个有 n 个节点和 m 个边的有向图,所有边都具有一定的权重。

可能存在多条边和自环,并且图也可能断开。

您需要在图中选择一条路径(可能多次经过相同的顶点),使得边的权重严格按递增顺序排列,并且这些边按输入的顺序排列。在所有此类路径中,您需要找到具有最大可能边数的路径,并报告该值。

请注意,拾取的边在输入中不必是连续的。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 100000,1 ≤ m ≤ 100000) – 分别是图中的顶点和边的数量。

m 行如下。

这些行中的第 i 行包含三个空格分隔的整数 ai、bi 和 wi (1 ≤ ai, bi ≤ n, 0 ≤ wi ≤ 100000),表示从顶点 ai 到顶点 bi 的一条边,其权重为 wi

输出

在一行中打印一个整数 — 路径中的最大边数。

示例

输入 #1

3 3
3 1 3
1 2 1
2 3 2

输出 #1

2

输入 #2

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

输出 #2

3

注意

第一个样本输入的答案是 2:$$1 \rightarrow 2 \rightarrow 3$$。请注意,您无法遍历 $$1 \rightarrow 2 \rightarrow 3 \rightarrow 1$$,因为边 $$\overset{3}{\rightarrow}1$$ 在输入中出现得比其他两条边更早,因此无法在其他两条边之后拾取/遍历。

在第二个示例中,最好选择第 1、第 3 和第 5 条边来获得最佳答案:$$1 \rightarrow 3 \rightarrow 4 \rightarrow 5$$。