Quả là trái dừa đã cho Khánh một ý tưởng thiên tài khi chuyển sang bán cocktail. Bây giờ Khánh đã mở rộng mạng lưới của mình sang khắp các hòn đảo bên cạnh. Tại mỗi hòn đảo, anh mở một cửa hàng cocktail. Tùy theo sản vật của từng hòn đảo mà mỗi cửa hàng chuyên về một loại cocktail nhất định. Tuy nhiên, do hệ thống đường nối các hòn đảo với nhau vẫn chưa được cải thiện (vẫn dùng các cây cầu dừa để vừa đủ cho từ mỗi hòn đảo chỉ có một đường đi duy nhất đến mọi hòn đảo khác) nên khi giao hàng cho khách gặp một vấn đề nho nhỏ: nhiều khi khách hàng lại không muốn thưởng thức sản phẩm trên hòn đảo của mình mà lại muốn dùng những loại cocktail khác. Để tiết kiệm chi phí đi lại, Pirate phải chọn cửa hàng cung ứng loại cocktail tương ứng gần với hòn đảo của người khách nhất để đi giao hàng...

Input

• Dòng thứ nhất: ghi số nguyên \(n\) là số hòn đảo.
• \(n-1\) dòng tiếp theo: mỗi dòng ghi hai số nguyên \(x\) và \(y\) thể hiện có một cây cầu dừa nối hai hòn đảo \(x\) và \(y\).
• Dòng thứ \(n+1\): ghi số nguyên \(c\) là số loại cocktail mà các cửa hàng cung ứng.
• Dòng thứ \(n+2\): ghi \(n\) số nguyên là loại cocktail chuyên biệt của từng hòn đảo (từ đảo \(1\) đến đảo \(n\)).
• Dòng thứ \(n+3\): ghi số nguyên \(m\) là số các vị khách.
• \(m\) dòng tiếp theo: mỗi dòng mô tả hai số nguyên \(x\) và \(y\) thể hiện người khách ở đảo \(x\) yêu cầu cocktail loại \(y\).

Output

• Gồm \(m\) dòng, mỗi dòng ghi ra khoảng cách (tính bằng số cây cầu dừa) cửa hàng gần nhất phải đi để giao hàng cho người khách tương ứng.

Constraints

• \(1 \le c \le n \le 10^4\)
• \(1 \le m \le 10^4\)

Example

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

1
2
0
1
2
2
3
3