Cho mạng lưới ~N~ thành phố cấu trúc dạng cây. Mỗi truy vấn cho một tập ~S~ gồm ~K~ thành phố trọng yếu.

Chọn một thành phố ~u~ bất kỳ trên toàn bộ cây, sao cho tổng khoảng cách đến mọi thành phố trong ~S~ nhỏ nhất. Tính:

~M(S) = min_{u ∈ V} ∑_{v ∈ S} dist(u,v)~.

Khoảng cách là số cạnh trên đường đi ngắn nhất. Chỉ cần in giá trị nhỏ nhất, không cần in thành phố được chọ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 tổng khoảng cách nhỏ nhất ~M(S)~.

Ví dụ

Input

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

Output

3

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.