Задачі
Маршрути в горах
Маршрути в горах
Гірський туристичний комплекс складається з 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