Water on Tree

সময় লিমিট: 1.0 s

মেমরি লিমিট: 256.0 MB

Description

Friendship is one of the most precious things in the world. A true friendship is never broken. This kind of friendship suits Roy and his friend Hridoy. A few days ago, Hridoy faced a problem. The problem is very simple,

You are given a tree with N nodes. The root of the tree is 1. Intially, root node 1 fills up with the infinity-level water supply, and all other nodes are empty. Water flow starts at root node 1, and it takes exactly one second to reach any neighboring nodes.

You are also given Q query; in each query, you need to determine within X seconds how many nodes are filled up by water.

Unfortunately, Roy is busy with his assignment. As a well-wisher for Roy, can you solve this problem?

Input

First Line T, number of test cases.
In each test case,
First Line,N the number of nodes of the tree and Q the number of query.
Second Line, Exactly N-1 Edges, Between U and V.
Thrid Line, In each query an integer X.

\(1 <= T <= 1000\)
\(1 <= N ,Q , X <= 10^5\)
\(1 <= U , V <= N\)

It's gurantee that graph is a tree.
Sum of N and Q, over all test cases doesn't exceed \(2 * 10^5\).

Output

In each query, print the answer with a newline.

Sample

Input Output
1
5 5
1 2
2 3
3 4
1 5
1
2
3
4
5
3
4
5
5
5

Sample test case explaination:

Information

ID
1053
Difficulty
4
Category
Graph_Theory | DFS , BFS দেখানোর জন্য ক্লিক করুন
Tags
# Submissions
47
Accepted
21
Accepted Ratio
45%
Uploaded By

Related

In following contests:

Brain Booster #3