Cloudy Days#11645

Cloudy Days

1 second

128 megabytes

Medium

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 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 different 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

Example 1

Loading