Tý có một mạng xã hội gồm \(N\) người dùng được kết nối với nhau tạo thành một cấu trúc cây (gốc tùy ý, \(N-1\) kết nối). Mỗi người dùng có một sở thích được biểu diễn bằng một số nguyên dương. Hệ thống muốn thực hiện Q truy vấn: trên đường đi duy nhất giữa hai người dùng U và \(V\), có bao nhiêu sở thích khác nhau?

Hãy viết chương trình xử lý nhanh các truy vấn trên cây.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và Q (\(1 \le N, Q \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) — sở thích của người dùng thứ i (\(1 \le a_i \le 10^9\)). - N-\(1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một kết nối giữa hai người dùng (\(1 \le u, v \le N\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(U, V\) — truy vấn đường đi (\(1 \le U, V \le N\)).

Định dạng đầu ra

• In ra \(Q\) dòng, mỗi dòng là số sở thích khác nhau trên đường đi giữa U và \(V\).

Ví dụ

Input:

8 3
1 2 1 3 2 1 4 5
1 2
1 3
2 4
2 5
3 6
3 7
6 8
4 5
4 8
2 7

Output:

2
4
3

Subtask