Pashmak and Graph

题意翻译

给定n 个点，m 条带权边的有向图。 现在请你找一条路径，起点和终点自取，在保证路径上的边权严格递增（即 下一条边的v 严格大于上一条的v）的情况下包含最多的边。 每条边只用一次。请输出路径最多能包含多少条边。 第一行输入2个数字n,m, 表示n 个点m 条有向边。 第2 到m+1 行每行3 个数s,t 和v，表示边的起点、终点、边权。

题目描述

Pashmak's homework is a problem about graphs. Although he always tries to do his homework completely, he can't solve this problem. As you know, he's really weak at graph theory; so try to help him in solving the problem. You are given a weighted directed graph with $ n $ vertices and $ m $ edges. You need to find a path (perhaps, non-simple) with maximum number of edges, such that the weights of the edges increase along the path. In other words, each edge of the path must have strictly greater weight than the previous edge in the path. Help Pashmak, print the number of edges in the required path.

输入输出格式

输入格式

The first line contains two integers $ n $ , $ m $ $ (2<=n<=3·10^{5}; 1<=m<=min(n·(n-1),3·10^{5})) $ . Then, $ m $ lines follows. The $ i $ -th line contains three space separated integers: $ u_{i} $ , $ v_{i} $ , $ w_{i} $ $ (1<=u_{i},v_{i}<=n; 1<=w_{i}<=10^{5}) $ which indicates that there's a directed edge with weight $ w_{i} $ from vertex $ u_{i} $ to vertex $ v_{i} $ . It's guaranteed that the graph doesn't contain self-loops and multiple edges.

输出格式

Print a single integer — the answer to the problem.

输入输出样例

输入样例 #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

说明

In the first sample the maximum trail can be any of this trails: . In the second sample the maximum trail is . In the third sample the maximum trail is .