Hệ thống xác thực Binance

Trong tương lai xa tại hành tinh Binance, Liên minh Thiên hà đã xây dựng một hệ thống mạng lượng tử kết nối \(n\) trạm truyền tin liên hành tinh, các trạm truyền tin được đánh số liên tiếp từ \(1\) đến \(n\) \((1 \leq n \leq 10^5)\). Có \(n - 1\) liên kết kết nối giữa các cặp trạm truyền tin, liên kết thứ \(i\) sẽ kết nối hai trạm truyền tin \(u_i\) và \(v_i\) \((1 \leq u_i \neq v_i \leq n)\), liên kết này có giới hạn băng thông là \(w_i\) \((1 \leq w_i \leq 10^9)\). Hệ thống được thiết kế như một đồ thị cây, nghĩa là giữa bất kỳ hai trạm bất kỳ luôn tồn tại đúng một tuyến truyền dữ liệu duy nhất.

Khi truyền dữ liệu giữa hai trạm bất kỳ, giới hạn của đường truyền được xác định là giá trị nhỏ nhất trong tất cả các giới hạn băng thông trên đường đi.

Một mạng con Binance được định nghĩa là một nhóm các trạm mạng trên hệ thống. Mạng con, nói một cách cụ thể hơn, là mạng bao gồm các trạm truyền tin \(k_1, k_2, k_3, ..., k_m\) (với \(m\) là số lượng trạm truyền tin trong mạng). Để xác thực dữ liệu một cách mạnh mẽ nhất, các nhà khoa học muốn tìm ra cặp trạm \((k_i, k_j)\) trong mạng con sao cho đường truyền giữa chúng có giới hạn là lớn nhất trong tất cả các cặp --- gọi đó là đường kính của mạng Binance.

Để đánh giá được chất lượng của toàn bộ \(n\) trạm truyền tin trong mạng, ban đánh giá của mạng con này sẽ đưa ra \(Q\) phép thử, mỗi phép thử thứ \(i\) gồm \(m\) trạm truyền tin \(k_1, k_2, ..., k_m\). Với mỗi phép thử, bạn hãy tính toán đường kính của mạng con được cho.

Nhiệm vụ của bạn: Với mỗi mạng con Binance, hãy giúp họ xác định đường kính của mạng con này.

Input

• Dòng đầu chứa số nguyên \(n\) --- số trạm mạng \((1 \leq n \leq 10^5)\).
• \(n-1\) dòng tiếp theo, mỗi dòng gồm 3 số nguyên \(u_i, v_i, w_i\) --- mô tả kết nối trực tiếp giữa trạm \(u_i\) và \(v_i\) với giới hạn truyền tải \(w_i\) \((1 \leq u_i \neq v_i \leq n, 1 \leq w_i \leq 10^9)\).
• Dòng tiếp theo chứa số nguyên \(Q\) --- số phép thử cần xử lí \((1 \leq Q \leq 10^5)\).
• \(Q\) dòng tiếp theo, mỗi dòng có dạng \(m\ k_1\ k_2\ \dots\ k_m\) --- mô tả một mạng con gồm \(m\) trạm \((2 \leq m \leq n)\).

Output

Với mỗi truy vấn, in ra một dòng duy nhất là đường kính xác thực của mạng Binance tương ứng.

Example

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

4
1
5
3

Scoring

Gọi \(T\) là tổng số lượng đỉnh trong tất cả \(Q\) phép thử.

• Có \(10\%\) số test tương ứng với \(10\%\) số điểm có \(n, T \leq 100, Q = 1, m = n\), các trạm truyền tin trong phép thử đầu tiên là \(n\) trạm truyền tin trong đồ thị Binance.
• Có \(10\%\) số test tương ứng với \(10\%\) số điểm có \(n, T \leq 10^5, Q = 1, m = n\), các trạm truyền tin trong phép thử đầu tiên là \(n\) trạm truyền tin trong đồ thị Binance.
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n, T, Q \leq 100\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n, T, Q \leq 1000\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm \(n, T, Q \leq 10^5\), mỗi trạm truyền tin chỉ liên kết tối đa với \(2\) trạm truyền tin khác.
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm còn lại không có ràng buộc gì thêm.