LUXURY7

A.LittlePonyandExpectedMaximumTimeLimit:1000MSMemoryLimit:262144KB64bitIOFormat:%I64d 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.

Input

The first line contains two integers n, m(2 ≤ n ≤ 3·10⁵; 1 ≤ m ≤ min(n·(n - 1), 3·10⁵)). 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⁵) 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.

Output

Print a single integer — the answer to the problem.

Sample Input

Input3 31 2 12 3 13 1 1Output1Input3 31 2 12 3 23 1 3Output3Input6 71 2 13 2 52 4 22 5 22 6 95 4 34 3 4Output6

Hint

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 .

 一到很水的dp，只要知道原理，学过背包的都能做出来。     C - BoredomTime Limit:1000MS     Memory Limit:262144KB     64bit IO Format:%I64d  1 ≤ m ≤ 10⁵). The second line contains space-separated integers a₁, a₂, ..., a_n(1 ≤ a_i ≤ 10⁹).

Output

Print a single integer — the maximum final height of the smallest flower.

Sample Input

Input6 2 32 2 2 2 1 1Output2Input2 5 15 8Output9

Hint

In the first sample beaver can water the last 3 flowers at the first day. On the next day he may not to water flowers at all. In the end he will get the following heights: [2, 2, 2, 3, 2, 2]. The smallest flower has height equal to 2. It‘s impossible to get height 3 in this test.

 二分，并用pre[l] += 1 , pre[l+w] -= 1 ,来维护区间的变化，使判断的过程用O（n）实现。但用线段树的成段更新也能过。

LUXURY 7