You and your friend are playing the Game of Tree. You both are given a tree with N nodes numbered from 1 to N and N-1 edges. Initially both of you will select two different nodes and color the nodes. One will not use the same color as the other.
Then each next second both of you will color all the nodes that are adjacent to the nodes you have already colored. One can not color a node that is already colored by the other. If both arrive in a node at the same time that node remains uncolored. At the end one who has colored more nodes than the other wins.
As your friend has already selected his node, you know which node your friend has selected. You will have to tell whether you can win or not if you select your node optimally.
Input
The first line contains The number of test case T ( 1 ≤ T ≤ 105 ).
First line of each test case will contain two integers N ( 2 ≤ N ≤ 105 ), the number of nodes and K ( 1 ≤ K ≤ N ), the node selected by your friend.
Next N-1 lines will contain two integers u and v each meaning that there is an edge between node u and v.
It is guaranteed that the sum of N does not exceed 2⋅105 over all test cases.
Output
For each test case print the case number and “Yes” if you can win and “No” otherwise (without quotes). ( see the sample output for more details.)
Sample
| Input | Output |
|---|---|
2 5 4 1 2 3 4 2 4 1 5 3 1 1 2 1 3 | Case 1: Yes Case 2: No |
