You are given a tree with `n` vertices. The `i`-th vertex has a non-negative weight `w`_{i}.

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`,`v`_{1}, ...,`v`_{k},`y`, then either`w`_{x}≥`w`_{v1}≥ ... ≥`w`_{vk}≥`w`_{y}, or`w`_{x}≤`w`_{v1}≤ ... ≤`w`_{vk}≤`w`_{y}

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 `w`_{1}, `w`_{2}, ..., `w`_{n} (0 ≤ `w`_{i} ≤ 10^{9}).

Each of the following `n` - 1 lines describing edges contains two integers `u` and `v` (1 ≤ `u`, `v` ≤ `n`, `u` ≠ `v`) 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 ≤ `x` ≤ `n`, 0 ≤ `d` ≤ `n`).

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

提交代码