Meet people

4.4

11 votes
Graphs, Algorithms, Breadth-first search, Tree
Problem

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

  • The first line contains T denoting the number of test cases.
  • The first line of each test case contains integers N and K denoting the total node of tree and total number of people.
  • Next N1 lines of each test case contain two integers x and y (1x, yN). It means that there exists an edge connecting vertices x and y. It is guaranteed that using these edges always forms a tree.
  • The next line of each test case contains K distinct integers A[1],A[2], ..., A[K] where A[i] is the location of the ith person.

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

1T10

1N105
1KN

1A[i]N

 

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation
  1. Here person at node 1 go to node 2 and person at node 3 go to node 2. After 1 second they can meet. 
  2. There is only person so answer is 0.
Editor Image

?