Mountain routes

The mountain tourist resort consists of n hostels, connected with k mountain routes (other routes in mountains are dangerous). Any route between two hostels takes 1 day. The travel group, located in the hostel a, is going to go to the hostel b for no more than d days. How many different routes (without cycles) between a and b exist?

Input

The first line contains numbers n, k, a, b, d (n ≤ 50, d ≤ 10), separated with a space. Each of the next k lines contains pair of numbers that describes the possible mountain route. All given numbers are positive integers.

Output

Print one number - the number of routes.

Examples