Bạn được cung cấp một cây ~n~ đỉnh có ~n - 1~ cạnh, mỗi đỉnh mang một giá trị đại diện cho chúng. Và bạn phải trả lời ~q~ câu hỏi rằng trên đường đi đơn từ ~u~ đến ~v~ có bao nhiêu giá trị phân biệt?

Input

• Dòng đầu tiên là số nguyên ~n~ và ~q~, mô tả số lượng đỉnh và số lượng câu hỏi.
• Dòng thứ hai là ~n~ số nguyên ~a_1, a_2, ..., a_n~ là giá trị trên mỗi đỉnh.
• ~n - 1~ dòng tiếp theo là ~u~ và ~v~, mô tả rằng có đường đi từ ~u~ đến ~v~.
• ~q~ dòng tiếp theo, mỗi dòng gồm ~u~ và ~v~, bạn cần trả lời câu hỏi cho đường đi từ ~u~ đến ~v~.

Output

• ~q~ dòng mỗi dòng là câu trả lời của mỗi truy vấn.

Constraints

• ~1\le n, q \le 10^5~
• ~1 \le a_i \le 10^9~
• ~1 \le u \ne v \le n~

Input Sample 1

4 3
1 2 3 3
1 2
2 3
2 4
1 2
2 3
1 4

Output Sample 1

2
2
3

Input Sample 2

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

Output Sample 2

3
3