← Home
write a go solution for Description:
You are given a tree, consisting of n vertices. There are k chips, placed in vertices a_1,a_2,...,a_k. All a_i are distinct. Vertices a_1,a_2,...,a_k are colored black initially. The remaining vertices are white.

You are going to play a game where you perform some moves (possibly, zero). On the i-th move (1-indexed) you are going to move the ((i-1)bmodk+1)-st chip from its current vertex to an adjacent white vertex and color that vertex black. So, if k=3, you move chip 1 on move 1, chip 2 on move 2, chip 3 on move 3, chip 1 on move 4, chip 2 on move 5 and so on. If there is no adjacent white vertex, then the game ends.

What's the maximum number of moves you can perform?

Input Format:
The first line contains a single integer t (1<=t<=10^4) — the number of testcases.

The first line of each testcase contains a single integer n (1<=n<=2*10^5) — the number of vertices of the tree.

Each of the next n-1 lines contains two integers v and u (1<=v,u<=n) — the descriptions of the edges. The given edges form a tree.

The next line contains a single integer k (1<=k<=n) — the number of chips.

The next line contains k integers a_1,a_2,...,a_k (1<=a_i<=n) — the vertices with the chips. All a_i are distinct.

The sum of n over all testcases doesn't exceed 2*10^5.

Output Format:
For each testcase, print a single integer — the maximum number of moves you can perform.

Note:
None. Output only the code with no comments, explanation, or additional text.