题目内容

助手技能编排时，系统里有 $p$ 个技能节点（编号 $1$ 到 $p$）和 $q$ 条有向衔接。衔接按记录顺序给出：第 $i$ 条从节点 $x_i$ 指向 $y_i$，分值为 $s_i$。图中可以有自环和重边。

需要选一条由衔接组成的技能执行链，使包含的边数尽量多。链必须同时满足：

1. 记录下标严格递增：若先用第 $i$ 条衔接，下一条必须是某个 $j>i$。
2. 分值严格递增：后一条的 $s$ 必须大于前一条的 $s$。

请给出这样一条链最多能包含多少条边。

输入描述

首先一行两个整型 $p$ 和 $q$（$1 \le p,q \le 200000$），表示节点数与衔接数。

随后 $q$ 行，第 $i$ 行三个整型 $x_i,y_i,s_i$（$1 \le x_i,y_i \le p$，$0 \le s_i \le 200000$），表示一条 $x_i \to y_i$、分值为 $s_i$ 的有向衔接。

输出描述

写出一个非负整型，即最长合法执行链的边数。

样例1

输入

2 3
1 2 4
2 1 5
1 2 6

输出

3

说明

三条衔接分值 $4<5<6$，且终点接起点：$1\to 2\to 1\to 2$，下标也递增，故边数为 $3$。

样例2

输入

4 4
2 1 3
1 3 1
3 4 2
4 2 4

输出

3

说明

链 $1\to 3\to 4\to 2$ 使用第 $2$、$3$、$4$ 条衔接，分值 $1<2<4$。不能再接第 $1$ 条 $2\to 1$，因为它在输入中更早出现。