C. K-th LNCA
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

KaitoKid knows every algorithm known to mankind. As he really enjoys learning new algorithms, he is now waiting desperately for a new algorithm to be created by the grandmasters of the world so that he can learn something new.

He once realized that he is a grandmaster himself, so he wanted to create a new algorithm. He came up with an algorithm called $$$k$$$-th LNCA.

In a tree, A node $$$u$$$ is considered the parent of a node $$$v$$$ if there is an edge between $$$u$$$ and $$$v$$$ and $$$u$$$ is closer to the root than $$$v$$$.

A node $$$u$$$ is considered an ancestor of node $$$v$$$ if $$$u$$$ is reachable from $$$v$$$ by repeated proceeding from $$$v$$$ to its parent.

A node $$$u$$$ is considered a common ancestor of a subset of $$$m$$$ nodes $$$v_1, v_2 \dots v_m$$$ is a node that is an ancestor of each of the $$$m$$$ nodes.

A node $$$u$$$ is considered the lowest common ancestor (LCA) of a subset of $$$m$$$ nodes $$$v_1, v_2 \dots v_m$$$ if $$$u$$$ is the lowest node (I.e. furthest from the root) that is a common ancestor of the subset.

As per KaitoKid, to check if a node $$$u$$$ is a $$$k$$$-th lowest not so common ancestor ($$$k$$$-th LNCA) of a subset $$$S$$$ of $$$m$$$ nodes $$$v_1, v_2 \dots v_m$$$, you do the following:

  • Consider all of the subsets of $$$S$$$ that has exactly $$$k$$$ elements of $$$S$$$.
  • Consider having a set $$$S_1$$$ that has all of the LCAs of each of the above described subsets.
  • a node $$$u$$$ is a $$$k$$$-th LNCA if it is one of the lowest nodes (I.e. furthest from the root) in $$$S_1$$$.

After KaitoKid created this algorithm, he created a problem to train people on it. Given a tree of $$$n$$$ nodes rooted at $$$1$$$, you need to perform $$$q$$$ queries, in each query, you are given $$$k$$$, $$$m$$$ and a set of $$$m$$$ nodes $$$v_1, v_2 \dots v_m$$$, you need to find the number of nodes that are considered a $$$k$$$-th LNCA of the given set of nodes.

Input

The first line of the input contains a single integer number $$$t$$$ $$$(1 \le t \le 100)$$$. The number of test cases.

The first line of each test case contains two space-separated integer numbers $$$n$$$ and $$$q$$$ $$$(1 \le n, q \le 1000)$$$. The number of nodes in the tree and the number of queries you need to process, respectively.

The next $$$n-1$$$ lines of each test case each contains two space-separated integer numbers $$$a_i$$$ and $$$b_i$$$ $$$(1 \le a_i, b_i \le n)$$$, denoting having an edge between nodes $$$a_i$$$ and $$$b_i$$$. It is guaranteed that the given edges form a tree.

The next $$$q$$$ lines of each test case each contains space-separated integer numbers in the form $$$k\ m\ v_1\ v_2\ \dots v_m$$$ $$$(2 \le k \le m \le n)$$$. It is guaranteed that the nodes $$$v_1, v_2 \dots v_m$$$ are all distinct.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all of the test cases does not exceed $$$1000$$$.

Output

For each query in each test case print a single line containing a single integer number. The number of $$$k$$$-th LNCAs of the given set of nodes.

Example
Input
1
7 1
1 2
1 3
2 4
2 5
3 6
3 7
2 4 4 5 6 7
Output
2