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 Format:
- The input starts with three 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 Format:
Output a single integer representing the total possible number of cities Alice can reach if she uses up all K units of her fuel.
Constraints:
2≤N≤1030≤M≤(N∗(N−1))/21≤K≤1061≤C≤N
- Alice starts in city 1 with 2 units of fuel.
- She can move to city 5 using 1 unit of fuel (remaining fuel = 1).
- From city 5, she can reach city 3 using 1 unit of fuel (remaining fuel = 0).
- Alternatively, from city 5, she can reach city 2 using 1 unit of fuel (remaining fuel = 0).
At this point, Alice has 0 units of fuel and has reached cities 3 and 2. There are no further cities she can reach with her remaining fuel.
The total number of cities she can reach is {1, 5, 3, 2} through all possible paths.
So, the answer for the sample input, considering all possible paths, is 4.
