Given a tree of n vertices. Vertex i has number Ai on it.
You are also given q queries of the form u,x, find the distance of the nearest vertex having value x on it to u.
### Input
- The first line contains two integers n,q.
- The second line contains n integers Ai.
- The next n−1 lines, each line contains two integers u,v, there is an edge between u and v.
- The next q lines, each line contains two integers u,x, a query.
### Output
- Print the answer for each query, print -1 if no solution exists.
### Constraints
- 1≤n,q≤5×104.
- 1≤Ai,x≤n.
### Example
Input:
3212312132213
Output:
01