You are given a tree with $n$ nodes. Some nodes contain a coin.

Your task is to answer $q$ queries of the form: what is the shortest length of a path from node $a$ to node $b$ that visits all nodes with coins?

The first line contains two integers $n$ and $q$ : the number of nodes and queries. The nodes are numbered $1, 2, \dots, n$ .

The second line contains $n$ integers $c_1, c_2,\dots, c_n$ . If $c_i = 1$ , node $i$ has a coin. If $c_i = 0$ , node $i$ doesn't have a coin. You can assume at least one node has a coin.

Then there are $n-1$ lines describing the edges. Each line contains two integers $a$ and $b$ : there is an edge between nodes $a$ and $b$ .

Finally, there are $q$ lines describing the queries. Each line contains two integers $a$ and $b$ : the start and end nodes.

• $1 \le n, q \le 2 \cdot 10^5$
• $1 \le a, b \le n$

Print $q$ integers: the answers to the queries.