Zhautykov Olympiad 2020 Azerbaijan National Team Selection Contest Revisited
We are drunk
After the wedding ceremony, we – friends of Rashad decided to have some fun in the city. Renting a car, we started pushing the horn and riding freely,till the police noticed us! In our drunk imagination Baku consists of N points connected with N-1 roads, and there is exactly one path from one point to another. Also, there are exit points – they are connected to only one other point. It’s possible to exit Baku from these points, but police also tries to catch us. The polices can only start from the exit points, and we are currently at the point K. All police cars and our car moves with the same speed: in one minute,we can go from one point to the adjacent point. When our car intersects with a police car, we are caught. But. You are a spy and working for the police! So, you will tell the police which exit points they need to start, and you need to tell them the minimum number of exit points that they need to put a police car to be sure that they can catch us. Help the police!
The numbers N (1 ≤ N ≤
105 ) and K (1 ≤ K ≤ N) are given in the
first line. Each of next N-1 lines contain 2 numbers, the first endpoint of the road and the second endpoint of the road.
Print the minimum number of exit points you need to tell the points in order to make them sure to catch us.
Explanation for first test case
Putting polices to the exit nodes 2, 6, and 7 is needed to catch us.
7 1 1 2 1 3 3 4 3 5 4 6 5 7