Alice mới mua một đèn chùm để trang trí trong Lễ giáng sinh năm nay. Đèn chùm gồm ~n~ đèn được biểu diễn bằng một cây gồm ~n~ nút, trong đó các nút tương ứng với các đèn, các cạnh là khung sắt cùng dây nối giữa các đèn. Đèn ~i~ (~1 \le i \le n~) ở trạng thái ban đầu là màu ~c_i~ (~1 \le c_i \le 10^6~) và có thể điều chỉnh được, cụ thể, nếu một đèn đang ở trạng thái sáng màu ~c~ thì có thể điều chỉnh để đèn sáng màu ~c - 1~ nếu ~c > 1~ hoặc ~c + 1~ nếu ~c < 10^6~.

Alice đã tập hợp lại mong muốn của mọi người theo thứ tự ưu tiên giảm dần. Mong muốn thứ ~t~ (~1 \le t \le q~) là đoạn nối từ đèn ~u_t~ đến đèn ~v_t~ (~1 \le u_t, v_t \le n; u_t \ne v_t~) sẽ đối xứng, có nghĩa là khi liệt kê màu các đèn trên đường đi đơn từ đèn ~u_t~ đến đèn ~v_t~ cũng giống như liệt kê màu các đèn khi đi từ đèn ~v_t~ đến đèn ~u_t~.

Yêu cầu: Với mỗi giá trị ~t~, hãy giúp Alice tính số lần điều chỉnh ít nhất cần thực hiện từ trạng thái ban đầu để thỏa mãn mong muốn thứ ~t~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, q~ (~n, q \le 10^5~);
• Dòng thứ hai chứa ~n~ số nguyên dương ~c_1, c_2, \dots, c_n~ (~c_i \le 10^6~);
• Dòng thứ ~k~ trong ~n-1~ dòng sau chứa hai số nguyên dương ~u, v~ cho biết có dây nối trực tiếp giữa hai đèn ~u, v~ là cạnh của cây;
• Dòng thứ ~t~ chứa hai số nguyên dương ~u_t, v_t~ cho biết mong muốn thứ ~t~.

Output

• Gồm ~q~ dòng, dòng thứ ~t~ cho biết số lần điều chỉnh ít nhất cần thực hiện từ trạng thái ban đầu để thỏa mãn mong muốn thứ ~t~.