eolymp
Задачі

Маршрути в горах

Маршрути в горах

Гірський туристичний комплекс складається з n турбаз, з’єднаних між собою k гірськими переходами (інші маршрути в горах небезпечні). Кожен перехід між двома базами займає 1 день. Туристична група знаходиться на базі a і збирається потрапити на базу b не більш ніж за d днів. Скільки існує різних таких маршрутів (без циклів) між a і b?

prb122.gif

Вхідні дані

В першому рядку записані числа n, k, a, b, d (n50, d10). Кожен з наступних k рядків містить пару чисел, яка описує можливий гірський перехід. Усі числові значення натуральні.

Вихідні дані

Вивести одне число – кількість маршрутів.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
5 8 2 5 3
1 2
1 3
1 5
2 1
2 4
3 4
3 5
4 1
Вихідні дані #1
3
Автор Сергій Матвійчук
Джерело III етеп Всеукраїнської олімпіади з інформатики в Житомирській обл. 2006-2007 р