eolymp
bolt
Try our new interface for solving problems
Problems

Mountain routes

Mountain routes

Time limit 1 second
Memory limit 128 MiB

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?

prb122.gif

Input data

The first line contains numbers n, k, a, b, d (n50, d10), 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 data

Print one number - the number of routes.

Examples

Input example #1
5 8 2 5 3
1 2
1 3
1 5
2 1
2 4
3 4
3 5
4 1
Output example #1
3