Маршрути в горах
Гірський туристичний комплекс складається з n турбаз, з’єднаних між собою k гірськими переходами (інші маршрути в горах небезпечні). Кожен перехід між двома базами займає 1 день. Туристична група знаходиться на базі a і збирається потрапити на базу b не більш ніж за d днів. Скільки існує різних таких маршрутів (без циклів) між a і b?
Технічні умови
Вхідні дані
В першому рядку через проміжок записані числа n, k, a, b, d (n ≤ 50, d ≤ 10). Кожен з наступних k рядків містить пару чисел, яка описує можливий гірський перехід. Усі числові значення натуральні.
Вихідні дані
Вивести одне число – кількість маршрутів.
Інформація про задачу
Ліміт часу: 1 секундаЛіміт пам`яті: 64 MB
Бали за пройдений тест: 10
Складність: 35% 95/147
Класифікація: Пошук в глибину
Приклад
Приклад вхідних даних5 8 2 5 3 1 2 1 3 1 5 2 1 2 4 3 4 3 5 4 1 |
Приклад вихідних даних3 |
| ← CD-біржа | Список задач | Нулі в кінці запису N! → |