1447 - 最长上升路径

Time Limit: 3s Memory Limit: 128MB

Submissions: 133 Solved: 26
Description

给定n个顶点m条边的有向图,每一条边上都有一个正整数权值。一条有向路径被称为上升路径当且仅当除了路径上第一条边外,每一条表上的权值都严格大于路径上前一条边的权值。路径长度定义为路径所包含的边数,求给定图中最长上升路径长度。

Input

第一行是测试数据组数k。

接下来是k组测试数据。每组数据开始为n(n<=5000)和m(m<=100000)。接下来m行每行三个整数,表示图中一条边,格式为a b c,表示有一条从a到b的边,边权值为c。a和b是0到n-1的整数。

Output

每个测试数据输出一行。输出图中最长上升路径长度。

Sample Input
2
3 4
0 1 1
1 2 1
0 1 2
1 2 2
4 4
0 1 1
1 3 1
0 2 2
2 3 2
Sample Output
2
1
Hint

Source