Có một cây (đồ thị liên thông, vô hướng, không có chu trình) gồm $N$ đỉnh. Các đỉnh được đánh số từ $1$ đến $N$, các cạnh được đánh số từ $1$ đến $N-1$. Mỗi đỉnh có một trọng số.

Hãy viết chương trình thực hiện các truy vấn sau:

• u v: đưa ra số lượng trọng số khác nhau của các đỉnh nằm trên đường đi từ $u$ đến $v$.

Dữ liệu vào

Dòng đầu tiên chứa $N$ ($2 \le N \le 100{,}000$).

Dòng thứ hai chứa trọng số của các đỉnh theo thứ tự từ đỉnh $1$ đến đỉnh $N$.

$N-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ là hai đỉnh được nối bởi cạnh thứ $i$.

Dòng tiếp theo chứa số lượng truy vấn $M$ ($1 \le M \le 100{,}000$).

$M$ dòng tiếp theo, mỗi dòng chứa một truy vấn.

Trọng số của các đỉnh luôn là số tự nhiên không lớn hơn $1{,}000{,}000$.

Dữ liệu ra

Với mỗi truy vấn, in ra kết quả trên một dòng, theo thứ tự xuất hiện trong dữ liệu vào.

Ví dụ

Dữ liệu vào

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

Dữ liệu ra

4
4