You are given a tree of N nodes and K people located on the tree. You are also given an array A of size K where A[i] indicate the location of the ith person.
Now, there is an emergency meeting so all K people want to meet as soon as possible at the same node. In one second, a person who is standing at the ith node can go to any adjacent node of the ith node (the person cannot stand at the ith node and he or she has to move).
You are required to print the minimum time to meet all K people at the same node. If it is impossible to meet all K people at one node, then print -1.
Input format
Output format
For each test case, print the minimum time to meet all K people at the same node. If it is impossible to meet all K people at one node, then print -1 in new line.
Constraints
1≤T≤10
1≤N≤105
1≤K≤N
1≤A[i]≤N