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 (1N105 ) and K (1KN) 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.

Time limit 1 second
Memory limit 64 MiB
Input example #1
7 1
1 2
1 3
3 4
3 5
4 6
5 7
Output example #1
Source IZHO 2019-2020 Azerbaijan selection contest