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