K. Forced Online Queries?
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a tree of $$$N$$$ vertices rooted at vertex $$$1$$$ and a permutation $$$p$$$ of length $$$N$$$. For an array $$$\mathbf{a}$$$ of length $$$M$$$, we define the function $$$f(a)$$$ as the smallest size of a subgraph of the given tree that contains all the vertices $$$a_1, a_2, \dots, a_M$$$. We define $$$\text{dist}(u, v)$$$ as the number of edges on the path between vertices $$$u$$$ and $$$v$$$.

You have to answer $$$Q$$$ queries online, each query is of the following type:

  • $$$v$$$ $$$k$$$ : Let $$$S$$$ be the set of vertices $$$u$$$ such that $$$\text{dist}(1, u) = k$$$, and $$$v$$$ is an ancestor of $$$u$$$. Then we define the set $$$H$$$ as the set of vertices $$$p_u$$$ for all $$$u \in S$$$.

The answer to the query is $$$f(H)$$$.

Note the unusual input format.

Input

The first line contains a single positive integer number $$${1 \le T \le 10^5}$$$, the number of testcases.

The first line of each testcase contains two positive integers $$${1 \le N \le 10^5}$$$, $$${1 \le Q \le 5 \times 10^5}$$$.

The next line contains the permutation $$$p$$$.

Each of the following $$${N \space - \space 1}$$$ lines two positive integers $$$u$$$ and $$$v$$$ describing an edge connecting vertices $$$u$$$ and $$$v$$$.

Each of the following $$$Q$$$ lines describes a query in the following format:

  • Let $$$last$$$ be the answer to the last query, $$$($$$initially $$$last$$$ $$${= 0)}$$$. Then each line contains two positive integers $$$x$$$ and $$$y$$$, describing the query as $$${v = (x \space \space XOR \space \space last), \space k = (y \space \space XOR \space \space last)}$$$.

It is guaranteed that the sum of $$$N$$$ over all testcases does not exceed $$$10^5$$$, and that the sum of $$$Q$$$ over all testcases does not exceed $$${5 \times 10^5}$$$.

Output

For each query output the answer described in the statement in a separate line.

Example
Input
1
11 11
4 7 9 6 5 2 11 1 8 10 3
9 1
5 3
6 11
2 3
4 6
3 8
6 10
7 2
7 6
9 8
6 7
6 1
15 3
11 6
8 0
9 3
6 4
7 7
4 5
5 6
2 2
Output
5
4
1
1
1
1
1
1
1
1
1