Олимпиадный тренинг

Задача . ТР03. Задание 23. Ориентированный граф: количество путей


Задание выполняется с использованием прилагаемых файлов.

В текстовом файле описан ориентированный ациклический граф. Вершины графа обозначены натуральными числами. Номера вершин могут идти не подряд, а их числовой порядок не задаёт направление рёбер.

Каждая строка содержит два натуральных числа 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.

Пример имеет иллюстративный характер. Для выполнения задания используйте данные прилагаемого файла. Следует написать программу.