KTREEC - Bán hàng

Giới hạn
  • Thời gian: 0.4s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Quả là trái dừa đã cho Pirate một ý tưởng thiên tài khi chuyển sang bán cocktail. Bây giờ Pirate đã 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 - số hòn đảo.
  • N - 1 dòng tiếp theo: mỗi dòng ghi hai số nguyên x và y - 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 - số loại cocktail mà các cửa hàng cung ứng.
  • Dòng thứ N + 2: ghi N số nguyên - loại cocktail chuyên biệt của từng hòn đảo.
  • Dòng thứ N + 3: ghi số nguyên M - 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 - 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.

Giới hạn:

  • Trong mỗi test, 1 ≤ C ≤ N ≤ 10 4 , 1 ≤ M ≤ 10 4 .
  • 60% số test có 1 ≤ C ≤ 10 2 .

Example 

Input:
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

Output:
1
2
0
1
2
2
3
3

Giải thích: Chỉ có cửa hàng 3 chuyên về loại cocktail 4, nên kết quả chính là khoảng cách từ hòn đảo 3 đến các hòn đảo còn lại.

  • Người up: khanhptnk