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$$。