## CQM1TREE - Paths in a Tree

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 4Output: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) |