Tree Fun

All submissions for this problem are available.
David is a computer science student who loves his future profession. He is one of those who think that trees grow down, not up.
David likes connected undirected acyclic graphs, also known as trees. He especially likes solving problems about trees. Recently David found a piece of paper with a tree with N vertices drawn on it. He also found M queries on the same piece of paper, where each query was a nonempty list of some vertices of this tree. For each query, it was asked to find the number of vertices in the tree (which didn't belong to the list) such that if you removed this vertex and all edges incident to it from the tree, then all vertices from the list would belong to pairwise different connected components.
David spent seven unhappy days and six sleepless nights trying to solve this problem efficiently. He is still trying. As you're known to be a good problem solver, David's friend asked for your help. David won't sleep until he knows the answer to each query. Write a program which answers all the queries correctly.
Input
The first line of the input contains a single integer T, the number of test cases (no more than 5). Each test case is described as follows. The first line contains two integers N and M (2 ≤ N ≤ 50000, 1 ≤ M ≤ 50000), the number of vertices in the tree and the number of queries, respectively. N1 lines follow, describing the edges of the tree. The i^{th} line contains two integers X_{i} and Y_{i} (1 ≤ X_{i}, Y_{i} ≤ N, X_{i} ≠ Y_{i}), the indices of the vertices connected by the i^{th} edge. Then M lines follow, describing the queries. The i^{th} line contains an integer K_{i} (2 ≤ K_{i} ≤ N) followed by K_{i} distinct integers A_{i, j} (1 ≤ A_{i, j} ≤ N), the indices of the vertices in the i^{th} query.
It is guaranteed that the given graph is a tree in all the test cases. The sum of all K_{i} in each test case doesn't exceed 100000.
Output
For each test case output M lines containing a single integer each  the answer to the corresponding query from the input.
Example
Input: 1 5 3 1 2 1 3 1 4 4 5 2 2 5 3 2 3 4 3 1 3 5 Output: 2 1 0
Explanation
In the first query, vertex 1 is such a vertex. If you remove vertex 1 and all the edges that connect 1 to other vertices, then vertices 2 and 5 will belong to separate connected components. Similarly, vertex 4 is also valid.
In the second query, vertex 1 is the only valid vertex. If you remove vertex 1 and all the edges that connect 1 to other vertices, then the connected components will be {2}, {3} and {4, 5}. It's easy to see that vertices 2 and 3 will belong to separate components, vertices 3 and 4 will belong to separate components, and vertices 2 and 4 will belong to separate components.
In the third query, you cannot remove a single vertex from the set {2, 4} (and the corresponding edges) so that any pair of vertices from the set {1, 3, 5} will be in separate connected components.
Author:  gennady.korotkevich 
Tester:  gamabunta 
Tags  cook27, gennady.korotkevich, graph, lca 
Date Added:  18102012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP 6.3, CPP14, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 