Задание выполняется с использованием прилагаемых файлов.
В текстовом файле описан ориентированный ациклический граф. Вершины графа обозначены натуральными числами. Номера вершин могут идти не подряд, а их числовой порядок не задаёт направление рёбер.
Каждая строка содержит два натуральных числа A и B, разделённых пробелами. Такая строка означает, что в графе существует ориентированное ребро из вершины A в вершину B. Каждое ребро описано ровно один раз; строка с количеством вершин или рёбер отсутствует.
Путём из вершины X в вершину Y называется последовательность вершин, начинающаяся в X и заканчивающаяся в Y, в которой каждые две соседние вершины соединены ориентированным ребром в направлении следования. Два пути считаются различными, если различаются последовательности их вершин.
Граф не содержит ориентированных циклов. Всего в нём не более 10 000 вершин и не более 100 000 рёбер; номера вершин не превышают 10 000.
Определите количество различных путей из вершины 17 в вершину 1943. Гарантируется, что хотя бы один такой путь существует. В ответе запишите целое число.
Типовой пример организации данных в файле
1 2
1 3
2 4
3 4
2 3
4 5
В этом примере из вершины 1 в вершину 5 ведут три пути: 1–2–4–5, 1–3–4–5 и 1–2–3–4–5.
Пример имеет иллюстративный характер. Для выполнения задания используйте данные прилагаемого файла. Следует написать программу.