Background

Originally bzoj2589.

Problem Description

Given a tree with $n$ nodes, each node has an integer value. The value on node $i$ is $val_i$.

There are $m$ queries. Each query gives $u', v$. You need to decrypt them to get $u, v$, and then ask: how many distinct integers are on the path from $u$ to $v$.

Decryption method: $u = u' \operatorname{xor} lastans$.

Here, $lastans$ is the answer to the previous query. If there is no previous query, it is $0$.

Input Format

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers. The $i$-th integer represents $val_i$.

In the next $n - 1$ lines, each line contains two integers $u, v$, describing an edge.

In the next $m$ lines, each line contains two integers $u', v$, describing a query.

Output Format

For each query, output one integer per line, which is the answer.

8 2
105 2 9 3 8 5 7 7 
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5
3 8

4
4

Hint

For $100\%$ of the testdata, $1 \le u, v \le n \le 4 \times 10^4$, $1 \le m \le 10^5$, $0 \le u', val_i < 2^{31}$。

Translated by ChatGPT 5