You are given a tree that contains $N$ nodes, where every node $i$ is colored with some color $C_i$.

The distance of a node $V$ from a node $U$ is defined as the number of edges along the simple path from the node $U$ to the node $V$. Your task is to answer $M$ queries of the following type:

• $K$ $C$: Determine the distance of most distant node of color $C$ from node $K$. If there is no node of color $C$ in the tree, then print $-1$.

Input format

• First line: Two integers $N$ and $M$
• Next line: $N$ space-separated integers, where the $i^{th}$ integer is $C_i$ denoting the color of the $i^{th}$ node
• Next $N-1$ lines: Two integers $U$ and $V$ representing an edge between nodes $U$ and $V$
• Next $M$ lines: Two integers $K$ and $C$

Output format

For each query, print the distance of most distant node of color $C$ from the node $K$.
The answer for each query should come in a new line.

Input Constraints

$1 \le N, M \le 5 \times10^5$

$1 \le C_i \le 5 \times10^5$

$1 \le U, V \le N$

$1 \le K \le N$

$1 \le C \le 5 \times10^5$