Flóra và mẹ tìm thấy một cây phủ đầy bụi dưới tấm thảm. Cây có \(N\) đỉnh được đánh số từ \(1\) đến \(N\), nối với nhau bằng \(N-1\) cạnh.

Để làm sạch cây, mẹ của Flóra lặp lại thao tác sau: chọn hai lá khác nhau rồi làm sạch tất cả các cạnh trên đường đi ngắn nhất giữa hai lá đó. Một đỉnh là lá nếu nó có đúng một cạnh nối với đỉnh khác. Nếu đường đi có \(d\) cạnh thì chi phí làm sạch đường đi là \(d\). Cây được làm sạch khi mọi cạnh đã được làm sạch; tổng chi phí là tổng chi phí của các đường đi đã chọn. Mỗi lá chỉ được chọn làm đầu mút nhiều nhất một lần.

Flóra xét \(Q\) phiên bản của cây ban đầu. Trong phiên bản thứ \(i\), cô thêm tổng cộng \(D_i\) lá mới. Mỗi lá mới được tạo bằng cách chọn một đỉnh của cây ban đầu và nối đỉnh đó với lá mới bằng một cạnh. Có thể thêm nhiều lá vào cùng một đỉnh. Trong quá trình thêm lá, một số đỉnh ban đầu có thể không còn là lá.

Mỗi phiên bản bắt đầu lại từ cây ban đầu. Với từng phiên bản, hãy tìm chi phí nhỏ nhất để làm sạch toàn bộ cây. Nếu không thể làm sạch cây, in \(-1\).

Dữ liệu vào

Dòng đầu gồm hai số nguyên \(N,Q\).

Mỗi dòng trong \(N-1\) dòng tiếp theo gồm hai số nguyên \(u,v\), cho biết có một cạnh nối hai đỉnh \(u\) và \(v\) trong cây ban đầu.

Mỗi phiên bản được mô tả trên một dòng. Số đầu tiên là \(D_i\), tiếp theo là \(D_i\) số nguyên \(a_j\); mỗi số cho biết có một lá mới được nối với đỉnh \(a_j\) của cây ban đầu.

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(i\) là chi phí nhỏ nhất để làm sạch phiên bản thứ \(i\), hoặc \(-1\) nếu không thể.

Ví dụ

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

-1
10
8

Ràng buộc

• \(3\le N\le10^5\).
• \(1\le Q\le10^5\).
• \(1\le u,v\le N\).
• \(1\le D_i\le10^5\) với mọi \(i\).
• \(\sum_{i=1}^{Q}D_i\le10^5\).
• \(1\le a_j\le N\) với mọi lá được thêm.

Phân nhóm

1. \(0\) điểm: Bộ dữ liệu mẫu.
2. \(9\) điểm: \(Q=1\), cây ban đầu là hình sao tâm \(1\) (có cạnh nối \(1\) với mọi đỉnh \(2,3,\ldots,N\)), và không thêm lá nào vào đỉnh \(1\).
3. \(9\) điểm: \(Q=1\), cây ban đầu là đường đi \(1-2-\cdots-N\), và không thêm lá nào vào đỉnh \(1\) hoặc đỉnh \(N\).
4. \(16\) điểm: \(N\le20000\) và \(Q\le300\).
5. \(19\) điểm: Cây ban đầu là cây nhị phân hoàn hảo có gốc tại đỉnh \(1\): mỗi đỉnh trong có đúng hai con và mọi lá cách gốc cùng một khoảng cách.
6. \(17\) điểm: \(D_i=1\) với mọi \(i\).
7. \(30\) điểm: Không có ràng buộc nào khác.