Cho vương quốc cấu trúc dạng cây gồm ~N~ đỉnh. Với mỗi truy vấn độc lập, đặt ~K~ trung tâm cứu trợ tại các đỉnh phân biệt của tập ~S~.

Mỗi đỉnh trên toàn bộ cây thuộc quyền quản lý của trung tâm gần nhất, với khoảng cách tính bằng số cạnh. Nếu có nhiều trung tâm cùng khoảng cách nhỏ nhất, chọn trung tâm có chỉ số đỉnh nhỏ nhất.

Tính số đỉnh thuộc quyền quản lý của từng trung tâm. In kết quả đúng thứ tự các trung tâm xuất hiện trong dữ liệu vào, không phải thứ tự chỉ số tăng dần.

Dữ liệu vào

• Dòng đầu chứa số nguyên ~N~ (~1 ≤ N ≤ 200000~).
• ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ mô tả một cạnh vô hướng của cây. Các đỉnh đánh số từ ~1~ đến ~N~; mỗi cạnh có độ dài ~1~.
• Dòng tiếp theo chứa số nguyên ~Q~ (~1 ≤ Q ≤ 200000~).
• Tiếp theo là ~Q~ truy vấn độc lập. Mỗi truy vấn gồm một dòng chứa ~K~ (~1 ≤ K ≤ N~), tiếp theo là ~K~ số nguyên phân biệt ~x_1, x_2, …, x_K~ (~1 ≤ x_i ≤ N~) mô tả tập ~S~.

Kết quả

Với mỗi truy vấn, in ~K~ số nguyên trên một dòng; số thứ ~i~ là số đỉnh do trung tâm ~x_i~ quản lý.

Ví dụ

Input

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

Output

5 3 2

Ràng buộc

• Subtask 1: ~N, Q ≤ 1000~.
• Subtask 2: ~∑K ≤ 200000~.

Quy cách chấm

Đọc từ đầu vào chuẩn, ghi ra đầu ra chuẩn. Có 50 test độc lập, mỗi test 2 điểm; tổng điểm là 100. Không chấm theo batch. Thời gian: 3 giây; bộ nhớ: 512 MiB.

Nguồn: Lưu Hải Phong — hpcode.edu.vn.