경로 걷기

n개의 노드와 m개의 간선으로 이루어진 방향 그래프가 주어지며, 모든 간선에는 특정 가중치가 있다.

다중 간선과 자기 루프가 존재할 수 있으며, 그래프가 연결되어 있지 않을 수도 있다.

그래프에서 경로 하나를 선택해야 한다(같은 정점을 여러 번 지날 수도 있다). 이때 간선의 가중치는 엄격한 증가 순서여야 하며, 이 간선들은 입력 순서대로 나타나야 한다. 이러한 모든 경로 중에서 가능한 간선 수가 최대인 경로를 찾아 그 값을 출력해야 한다.

선택한 간선들이 입력에서 연속할 필요는 없다는 점에 유의하라.

첫째 줄에 두 정수 n와 m (1 ≤ n ≤ 100000,1 ≤ m ≤ 100000)가 주어진다. 각각 그래프의 정점 수와 간선 수를 나타낸다.

이후 m개의 줄이 주어진다.

이 줄들 중 i-th에는 공백으로 구분된 세 정수 ai, bi, wi (1 ≤ ai, bi ≤ n, 0 ≤ wi ≤ 100000)가 주어지며, 이는 정점 ai에서 정점 bi로 향하고 가중치가 wi인 간선을 나타낸다.

한 줄에 정수 하나, 즉 경로에 포함될 수 있는 간선 수의 최댓값을 출력한다.

첫 번째 예제 입력의 답은 2이다: . 간선 은 다른 두 간선보다 입력에서 먼저 나타나므로, 다른 두 간선 중 어느 하나를 선택하거나 지난 뒤에는 을 지날 수 없음에 유의하라.

두 번째 예제에서는 최적의 답 을 얻기 위해 1-st, 3-rd, 5-th 간선을 선택하는 것이 최적이다.