问题 26974. -- 尿神学图论

26974: 尿神学图论

时间限制: 1 Sec  内存限制: 128 MB
献花: 21  解决: 1
[献花][花圈]

题目描述

尿神的功课是关于图形的一个问题,可是由于尿神天天忙于秀恩爱,无暇顾及功课,所以他希望你能帮他解决这个问题。

现有一个加权有向图有n个顶点和m条边。你需要找到一条最长的路径,使得沿着所述路径的边的重量严格递增。求出最长路径的边数(路径长度为路径所包含的边数)。

输入

第一行包含两个整数NM2N3·10^5; 1MminN·(N - 1),3·10^5))。紧接着有M行,第i行有三个空格隔开的整数:UVW1UVN1W10^5),表示从点U到点V有一条权值为W的边。处理到文件结尾。

保证了图形不包含重边。

输出

求出最长路径的边数。

样例输入

3 3
1 2 1
2 3 2
3 1 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

提示

来源

[献花][花圈]