Сегодняшняя домашняя работа Пашмака — это задача на графы. Несмотря на то, что он всегда старается выполнить домашнюю работу полностью, эту задачу решить он не может. К сожалению, он не силен в теории графов. Пожалуйста, помогите ему.
Задан взвешенный ориентированный граф с n вершинами и m ребрами. Найдите длиннейший по количеству ребер путь, веса ребер в котором возрастают вдоль пути. Другими словами, у каждого ребра в пути должен быть строго больший вес, чем у предыдущего ребра пути.
Выведите длину описанного пути.
Выходные данные
Выведите единственное целое число — ответ на задачу.
Примечание
В первом примере подходит любой из путей: 
.
Во втором примере оптимальный путь: 
.
В третьем примере оптимальный путь: 
.
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2 1
2 3 1
3 1 1
|
1
|
|
2
|
3 3
1 2 1
2 3 2
3 1 3
|
3
|
|
3
|
6 7
1 2 1
3 2 5
2 4 2
2 5 2
2 6 9
5 4 3
4 3 4
|
6
|