Cho một cây với trọng số trên mỗi đỉnh và một tập con \(Q\) các đỉnh của cây, hãy tìm tập độc lập có tổng
trọng số lớn nhất trong \(Q\).

Input

• Dòng đầu chứa một số \(T \le 20\) là số lượng bộ test;

• Mỗi test có cấu trúc như sau:

• Dòng đầu chứa \(2\) số \(n\) và \(m\) là số đỉnh và số cạnh của đồ thị;

• Dòng thứ \(2\) chứa \(n\) số là trọng số trên mỗi đỉnh;
• Từ dòng \(3\) đến dòng \(m + 2\), mỗi dòng chứa \(2\) số là các cặp đỉnh có cạnh nối giữa chúng, dữ liệu
  đảm bảo đồ thị đã cho là \(1\) cây;

• Dòng \(m + 3\) chứa \(1\) số nguyên \(q\) là số truy vấn, sau đó mỗi dòng trong số \(q\) dòng tiếp chứa \(1\) dãy số:

  – Số đầu tiên trong dãy \(k\) chỉ số lượng của tập đỉnh truy vấn:

  – \(k\) số tiếp theo chỉ số hiệu từng đỉnh trong tập (đánh số từ \(0\)) là những đỉnh xét đến trong \(n\) đỉnh ban đầu

Output

• Mỗi truy vấn in ra \(1\) kết quả là trọng số tập độc lập lớn nhất trên \(1\) dòng. Sau mỗi một bộ test thì in ra
  một dòng trống.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(5 \le n \le 30, 1 \le q \le 100\);
• Subtask \(2\) (\(25\%\) số điểm): \(10 \le n \le 200, 100 \le q \le 1000\);
• Subtask \(3\) (\(25\%\) số điểm): \(150 \le n \le 200, q = 1000\).

Example

1
3 2
5 4 10
0 2
2 1
1
2 2 1

10