Cho một cây có \(n\) đỉnh. Một số đỉnh chứa một đồng xu.

Nhiệm vụ của bạn là trả lời \(q\) truy vấn dạng: độ dài ngắn nhất của một đường đi từ đỉnh \(a\) đến đỉnh \(b\) có đi qua tất cả các đỉnh chứa xu là bao nhiêu?

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\): số đỉnh và số truy vấn. Các đỉnh được đánh số \(1, 2, \dots, n\).

Dòng thứ hai chứa \(n\) số nguyên \(c_1, c_2,\dots, c_n\). Nếu \(c_i = 1\), đỉnh \(i\) có xu. Nếu \(c_i = 0\), đỉnh \(i\) không có xu. Bạn có thể giả sử rằng có ít nhất một đỉnh có xu.

Sau đó có \(n-1\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có một cạnh giữa hai đỉnh \(a\) và \(b\).

Cuối cùng có \(q\) dòng mô tả các truy vấn. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): đỉnh bắt đầu và đỉnh kết thúc.

Output

In ra \(q\) số nguyên: đáp án của các truy vấn.

Constraints

• \(1 \le n, q \le 2 \cdot 10^5\)

• \(1 \le a, b \le n\)

Example

5 4
1 0 0 1 0
2 4
2 3
1 3
3 5
1 5
3 2
4 4
5 5

6
5
6
8