Cho một vương quốc hình cây gồm \(N\) đỉnh và \(N - 1\) cạnh vô hướng, độ dài mỗi cạnh đều bằng \(1\). Các đỉnh được đánh số từ \(1\) đến \(N\). Bạn cần xử lý \(Q\) truy vấn độc lập, mỗi truy vấn cung cấp một tập hợp \(S\) gồm \(K\) thành phố trọng yếu (\(S = \left\{ x_{1},x_{2},\ldots,x_{K} \right\}\)).

Yêu cầu: Với mỗi truy vấn, hãy tìm khoảng cách lớn nhất giữa hai thành phố bất kỳ thuộc tập \(S\). Nói cách khác, hãy tìm “đường kính” thu hẹp của tập \(S\):

\[D_{\max}(S) = \max_{1 \leq i < j \leq K}{\text{dist}\left( x_{i},x_{j} \right)}\]

Trong đó \(\text{dist}(u,v)\) là số cạnh trên đường đi ngắn nhất giữa hai đỉnh \(u\) và \(v\) trên cây gốc.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) (\(1 \leq N,Q \leq 2 \cdot 10^{5}\)).

• \(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 của cây.

• Tiếp theo là \(Q\) nhóm dòng, mỗi nhóm mô tả một truy vấn:

  • Dòng đầu chứa số nguyên \(K\) – số lượng thành phố trong tập \(S\) (\(1 \leq K \leq N\)).

  • Dòng tiếp theo chứa \(K\) số nguyên phân biệt \(x_{1},x_{2},\ldots,x_{K}\) (\(1 \leq x_{i} \leq N\)).

Kết quả:

• Với mỗi truy vấn, in ra một số nguyên duy nhất là giá trị \(D_{\max}(S)\). Nếu \(K = 1\), kết quả mặc định là \(0\).

Ví dụ:

Ràng buộc:

• Subtask 1 (20% số điểm): \(N,Q \leq 100\), \(K \leq N\).

• Subtask 2 (30% số điểm): \(N,Q \leq 2000\), tổng số lượng đỉnh trong tất cả các truy vấn thỏa mãn \(\sum_{}^{}K \leq 4000\).

• Subtask 3 (25% số điểm): \(N,Q \leq 2 \cdot 10^{5}\), hình dạng cây gốc là một đường thẳng đơn tuyến (Line Graph: Đỉnh \(i\) nối với \(i + 1\)).

• Subtask 4 (25% số điểm): \(N,Q \leq 2 \cdot 10^{5}\), tổng số lượng đỉnh trong tất cả các truy vấn thỏa mãn \(\sum_{}^{}K \leq 2 \cdot 10^{5}\), cấu trúc cây gốc ngẫu nhiên bất kỳ.