Cloudy Days

Alice is navigating the country of Cloudland on a cloudy day, making it challenging to see her way. She has a car with $k$ units of fuel remaining, where each unit of fuel allows her to travel a distance of $1$ unit.

Given the country's layout, consisting of several interconnected cities, and her current location, your task is to determine and print the total possible number of cities she can visit reach if she exhausts all her fuel.

Input

The first line contains four integers:

• $n$: the number of cities in Cloudland.

• $m$: the number of roads connecting differenct cities in Cloudland

• $k$: the remaining fuel units in Alice's car.

• $c$: Alice's current city

The following $m$ lines describe the road connections between cities as pairs of integers $u,v$, indicating a bidirectional road between cities $u$ and $v$.

Output

Output a single integer representing the total possible number of cities Alice can reach if she uses up all $k$ units of her fuel.

Examples