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

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

Вхідні дані

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

Вихідні дані

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

Приклади