CF960F.Pathwalks

You are given a directed graph with n nodes and m edges, with all edges having a certain weight.

There might be multiple edges and self loops, and the graph can also be disconnected.

You need to choose a path (possibly passing through same vertices multiple times) in the graph such that the weights of the edges are in strictly increasing order, and these edges come in the order of input. Among all such paths, you need to find the the path that has the maximum possible number of edges, and report this value.

Please note that the edges picked don't have to be consecutive in the input.

给你一个包含 $n$ 个节点和 $m$ 条边的有向图，每条边具有一定的权重。

图中可能存在重边和自环，且该图也可能是不连通的。

你需要在图中选择一条路径（允许重复经过同一顶点），使得所选边的权重严格递增，且这些边在输入中的出现顺序与所选顺序一致。在所有满足条件的路径中，你需要找出边数最多的那条路径，并输出该最大边数。

请注意：所选的边在输入中不必连续出现。

The first line contains two integers n and m (1 ≤ n ≤ 100000,1 ≤ m ≤ 100000) — the number of vertices and edges in the graph, respectively.

m lines follows.

The i-th of these lines contains three space separated integers a__i, b__i and w__i (1 ≤ a__i, b__i ≤ n, 0 ≤ w__i ≤ 100000), denoting an edge from vertex a__i to vertex b__i having weight w__i

第一行包含两个整数 $n$ 和 $m$（$1 ≤ n ≤ 100000$，$1 ≤ m ≤ 100000$），分别表示图中顶点和边的数量。

接下来有 $m$ 行。

第 $i$ 行包含三个以空格分隔的整数 $a_i$、$b_i$ 和 $w_i$（$1 ≤ a_i, b_i ≤ n$，$0 ≤ w_i ≤ 100000$），表示一条从顶点 $a_i$ 指向顶点 $b_i$、权重为 $w_i$ 的有向边。

Print one integer in a single line — the maximum number of edges in the path.

在一行中输出一个整数——该路径中边的最大数量。

The answer for the first sample input is 2: . Note that you cannot traverse because edge appears earlier in the input than the other two edges and hence cannot be picked/traversed after either of the other two edges.

In the second sample, it's optimal to pick 1-st, 3-rd and 5-th edges to get the optimal answer: .

第一个样例输入的答案是 2：。注意，你不能遍历 ，因为边 在输入中出现得比另外两条边更早，因此无法在另外两条边中的任意一条之后被选取/遍历。

在第二个样例中，最优策略是选取第 1、第 3 和第 5 条边，从而得到最优答案：。