给你一个有 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$$。