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