Задачи
Горные маршруты
Горные маршруты
Горный туристический комплекс состоит из n турбаз, соединенных между собой k горными переходами (другие маршруты в горах опасны). Любой переход между двумя базами занимает 1 день. Туристическая группа находится на базе a и собирается попасть на базу b не более чем за d дней. Сколько существует разных таких маршрутов (без циклов) между a и b?
Входные данные
В первой строке записаны числа n, k, a, b, d (n ≤ 50, d ≤ 10). Каждая из следующих k строк содержит пару чисел, которая описывает возможный горный переход. Все числовые значения натуральные.
Выходные данные
Вывести одно число - количество маршрутов.
Пример
Входные данные #1
5 8 2 5 3 1 2 1 3 1 5 2 1 2 4 3 4 3 5 4 1
Выходные данные #1
3