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