Максимальное число переходов
Во входных данных содержится описание ациклического ориентированного взвешенного графа. Каждая строка задаёт одно ребро: в ней записаны номера вершин и и вес ребра, ведущего из вершины в вершину . Любые две вершины соединены не более чем одним ребром.
Найдите наибольшее количество рёбер, которое может содержать путь из вершины с номером в вершину с номером . Веса рёбер на ответ не влияют. Существование хотя бы одного такого пути гарантируется.
Входные данные
Входные данные содержат не более строк; читать их нужно до конца ввода. В каждой строке записаны два натуральных числа и и положительное вещественное число (, , ). Числа в строке разделены произвольным ненулевым количеством пробелов и (или) табуляций.
Вершины графа могут быть пронумерованы не подряд, а ребро может вести в вершину с меньшим номером. Вес записан ровно с одной цифрой после десятичной точки.
Выходные данные
Выведите одно целое число — наибольшее количество рёбер в пути.
Примеры
11 97 0.1 11 53 9999.9 53 29 9999.9 29 97 9999.9
3
11 97 9999.9 11 53 0.1 53 29 0.1 29 97 0.1
3
Примечание
В обоих примерах путь 11, 53, 29, 97 содержит три ребра, а прямой путь — одно. Ответ равен 3 независимо от того, какой из этих путей имеет большую сумму весов.