Вам дан ориентированный граф с n вершинами и m рёбер, каждое из которых имеет определённый вес.
В нём могут быть кратные рёбра и петли, кроме того, граф может быть несвязным.
Вам нужно выбрать путь (возможно, проходящий по одному и тому же ребру или вершине несколько раз) такой, что веса рёбер в пути находятся в строго возрастающем порядке, а кроме того, все ребра пути идут в том же порядке, в котором они находились во входных данных. Найдите максимально возможное количество ребер в таком пути.
Обратите внимание, ребра пути не обязательно должны идти последовательно во входных данных.
Выходные данные
Выведите одно целое число в одной строке — максимальное количество рёбер в пути.
Примечание
Ответ на первый пример — 2: 
.
Заметим, что нельзя выбрать путь 
, потому что ребро 
появляется в вводе раньше, чем два других ребра, и поэтому его нельзя выбрать после того, как было выбрано какое-то из двух других рёбер.
Во втором примере оптимально выбрать 1-е, 3-е и 5-е ребра, чтобы получить оптимальный ответ: 
.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
3 1 3
1 2 1
2 3 2
|
2
|
|
2
|
5 5
1 3 2
3 2 3
3 4 5
5 4 0
4 5 8
|
3
|