Forgot Password ?
New password will be sent to following email id
Problem Code : VKISS
1 5 1 1 2 1 3 3 4 3 5
Time Limit :
C , C++ , Java
Login to submit your response.
Chotu and his girlfriend are out on a date in Civil Lines. On any normal day, this would be a great thing to do but this is the Valentine's Week and Bajrang Dal, a moral policing group active in Allahabad is notorius for troubling couples during this week. After their date, Chotu and his girlfriend need to rush back to IIITA before any Bajrang Dal activist catches them. <br><br> The map of Allahabad can be represented by <b>N</b> nodes that are connected by <b>N - 1</b> bidirectional roads. Civil Lines is located at node <b>K</b>. Also, it is known that there exists a unique path between every pair of nodes. Any node that has only one road connecting it is known as an exit node. Chotu and his girlfriend can escape safely if they reach an exit node without getting caught by an activist. An activist can start from any exit node and will attempt to catch Chotu. Both the activists and Chotu move at the same speed, i.e., in each step they can move from one node to any adjacent node. At all times, the activists know where Chotu is located currently and Chotu also knows the location of the activists as well. An activist can catch Chotu if at any instant they are at the same node as Chotu or crossing the same road.<br><br> You are the leader of Bajrang Dal and you have planned a raid to catch Chotu. Unfortunately, some members of your own group have deserted you and are out on dates with their respective girlfriends. Now you are worried that you might not have enough people to catch Chotu. You want to know the minimum number of activists that would be required in order to catch Chotu.
The first line of input denotes the number of test cases.<br> Each test case consists of <b>N</b> lines.<br> The first line of each test case contains two space-separated integers <b>N</b> and <b>K</b> which denote the number of nodes in Allahabad and the node where Civil Lines is located.<br> The following <b>N - 1</b> lines contain two space-separated integers, <b>X</b> and <b>Y</b> denoting that there exists a road between node <b>X</b> and node </b>Y</b>
Output a single line for each test case, denoting the minimum number of activists required to catch Chotu.
<b> 1 ≤ T ≤ 10 </b> <br> <b> 1 ≤ N ≤ 100000 </b> <br> <b> 1 ≤ K ≤ N </b> <br> <b> 1 ≤ X, Y ≤ N </b> <br>