Travel

Time Limit: 10 Seconds

Memory Limit: 524288 KB

Description

You are given a tree with n vertices. The i-th vertex has a non-negative weight wi.

You are given q quereis. For each query, you are given two integers x and d. You need to find the number of such vertex y that:

  • the distance from x to y is no larger than d.
  • let the path goes from x to y be x, v1, ..., vk, y, then either wxwv1 ≥ ... ≥ wvkwy, or wxwv1 ≤ ... ≤ wvkwy

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains two integers n and q (1 ≤ n, q ≤ 100000) — the number of vertices and the number of queries.

The second line contains n integers w1, w2, ..., wn (0 ≤ wi ≤ 109).

Each of the following n - 1 lines describing edges contains two integers u and v (1 ≤ u, vn, uv) meaning that there is a edge connecting vertex u and vertex v.

Each of the next q lines contains two integers x and d (1 ≤ xn, 0 ≤ dn).

It is guaranteed that the total number of vertices in the input doesn't exceed 5 × 105, and the total number of queries also doesn't exceed 5 × 105. The number of test cases in the input doesn't exceed 500.

Output

For each query, output the number of vertices.

Sample Input

1
3 3
1 2 3
1 2
2 3
2 0
2 2
1 1

Sample Output

1
3
2

Hint

None

Source

None

提交代码