CQM1TREE - Paths in a Tree

no tags 

Given a tree and a set of edges K, find total number of distinct paths in the tree consisting of all the edges in K. Two paths are distinct if the end nodes of the paths are different. Also, a path like (1->2->3) is same as (3->2->1).

A path is defined as a series of edges which connect a sequence of vertices which are all distinct.

Input

First line denotes the number of test cases T (<=100)
T test cases follow.
Each Test case is defined as:
First line contains n (1<=n<=2*10^4) and k (<=n-1) which are the number of nodes and size of the edge set, respectively.
n-1 lines follow, each defining an edge between pair of nodes u and v.
nodes are numbered 1 to n.
A single line consisting of k space separated indices (0-based, in order they appear in the input) of edges which are in the set.

Output

For each test case, output a single integer denoting the number of distinct paths in the tree consisting of all the edges in the set.

Example

Input:
3 
2 1
1 2
0
3 1
1 2
2 3
1
7 3
1 6
1 2
1 5
2 4
4 7
2 3
0 5 4 Output: 1
2
0

hide comments
Rishav Goyal: 2015-07-29 11:11:35

@mitch schwartz : I want to discuss things with you regarding spoj , could you please message me , i am sure u can access my email-id as u are moderator on spoj.


Added by:VV
Date:2015-01-28
Time limit:1.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Own problem (CQM 1, BIT Mesra)