eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Горные маршруты

Горные маршруты

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

prb122.gif

Входные данные

В первой строке записаны числа n, k, a, b, d (n50, d10). Каждая из следующих 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