I-To the Colors of the Dreams of Electric Sheep_2026牛客五一集训派对day1

时间限制：C/C++/Rust/Pascal 7秒，其他语言14秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

You are visiting a colorful tree in the dream of Electric Sheep, which has at most $60$ colors. These colors are numbered from $0$ to $59$ .

The colorful tree has $n$ vertices, connected with $n - 1$ edges. Each vertex is painted in some of the colors. Let non-negative integer $c_i$ denotes the colors of vertex $i$ . If the lowest $j$ -th bit of $c_i$ is $1$ , the colors that vertex $i$ is painted contains color $j$ . Note that a vertex can be painted in no colors, which means this vertex is transparent.

You also have your own color $c$ . When you are travelling on the colorful tree, you can visit vertex $i$ iff the colors of vertex $i$ contains your color $c$ . If you are at vertex $u$ and your color is $c$ , you can do one of the following operations in $1$ second:

Move to vertex $v$ that is adjacent to vertex $u$ .

Note that both the colors of vertex $u$ and those of vertex $v$ should contain color $c$ .
Choose a color $c'$ and change your color to $c'$ .

Note that the colors of vertex $u$ should contain both color $c$ and $c'$ .

Now you are planning for $q$ trips. The $i$ -th trip is planned from vertex $u_i$ to another vertex $v_i$ . You can choose any color you want as your color $c$ at vertex $u_i$ before the trip. Find out the number of seconds that need to be taken to arrive at vertex $v_i$ in the optimal way for each trip.

If you can’t reach vertex $v_i$ from vertex $u_i$ , print $-1$ .

输入描述:

The first line contains two positive integers $n$ , $q$ ( $2\leq n\leq 5\times 10^5$ , $1\leq q\leq 5\times 10^5$ ) — the number of vertices, and the number of trips.

The second line contains $n$ non-negative integers $c_1,c_2,\dots,c_n$ ( $0\leq c_i < 2^{60}$ ) — the colors of each vertex.

Each line in the following $n - 1$ lines contains two positive integers $u$ , $v$ ( $1\leq u,v\leq n$ ) — the edge connecting vertex $u$ and vertex $v$ .

Each line in the following $q$ lines contains two positive integers $u_i$ , $v_i$ ( $1\leq u_i,v_i\leq n$ , $u_i\neq v_i$ ) — the $i$ -th trip from vertex $u_i$ to vertex $v_i$ .

输出描述:

For each trip, print the number of seconds that need to be taken in the optimal way in a single line. If vertex $v_i$ is not reachable from vertex $u_i$ in the trip, print $-1$ .

示例1

输入

复制

10 8
12 9 14 5 1 18 18 9 14 7
1 3
2 3
2 4
3 6
4 10
5 8
7 9
8 9
8 10
1 7
3 8
4 5
5 6
6 1
8 10
9 2
10 5

输出

复制

示例2

输入

复制

输出

复制

-1
-1

备注:

In the first sample, the optimal way for the $3$ -rd trip from vertex $4$ to vertex $5$ is shown as followings:

Choose color $0$ as your own color before the trip at vertex $4$ .
Move to vertex $10$ from vertex $4$ . It takes $1$ second.
Move to vertex $8$ from vertex $10$ . It takes $1$ second.
Move to vertex $5$ from vertex $8$ . It takes $1$ second, and $3$ seconds in total.

The optimal way for the $5$ -th trip from vertex $6$ to vertex $1$ is shown as followings:

Choose color $1$ as your own color before the trip at vertex $6$ .
Move to vertex $3$ from vertex $6$ . It takes $1$ second.
Choose color $3$ and change your own color to it. It takes $1$ second.
Move to vertex $1$ from vertex $3$ . It takes $1$ second, and $3$ seconds in total.

In the second sample, it is not allowed to visit vertex $1$ , so you can’t start the trip at vertex $1$ . It is impossible to travel from vertex $2$ to vertex $3$ , because the colors of vertex $2$ and those of vertex $3$ share no colors.