Tajian đang giải quyết bài toán sau:
Cho một đồ thị gồm $n$ điểm, đồ thị ban đầu không có cạnh nào. Tajian có một số cạnh cần thêm vào đồ thị, và anh ấy đã chia các cạnh này thành $k$ nhóm, trong đó nhóm thứ $i$ chứa $c_i$ cạnh. Với mỗi $x \in [1, n]$, Tajian muốn biết số lượng nhóm cạnh tối thiểu mà anh ấy cần chọn từ $k$ nhóm này để thêm vào đồ thị nhằm đảm bảo số thành phần liên thông trong đồ thị không vượt quá $x$.
Mặc dù điều này không hiển nhiên ngay lập tức, có những bài báo khoa học chỉ ra rằng sắc số tối thiểu của cây khung là một bài toán NPC. Tuy nhiên, Tajian không biết điều này, vì vậy anh ấy muốn bạn giúp anh ấy giải bài toán này.
Dữ liệu vào
Một test đơn lẻ chứa nhiều bộ dữ liệu.
Dòng đầu tiên của dữ liệu vào là số lượng bộ dữ liệu $T$ ($1 \le T \le 10^3$), biểu thị số bộ dữ liệu trong test này.
Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa hai số nguyên $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), biểu thị số lượng điểm và số lượng nhóm cạnh.
Phần tiếp theo mô tả thông tin cho $k$ nhóm cạnh. Đối với nhóm cạnh thứ $i$, dòng đầu tiên chứa một số nguyên $c_i$ ($1 \le c_i \le 200$), biểu thị số lượng cạnh trong nhóm này. $c_i$ dòng tiếp theo mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le n, u \neq v$), biểu thị một cạnh trong nhóm này.
Đối với một bộ dữ liệu đơn lẻ, đảm bảo rằng $\sum c_i \le 200$. Đối với tất cả dữ liệu, đảm bảo rằng $\sum 2^n \le 2^{16}$.
Dữ liệu ra
Đối với mỗi bộ dữ liệu, in ra một dòng gồm $n$ số nguyên, trong đó số nguyên thứ $i$ biểu thị đáp án khi $x = i$.
Nếu không thể đảm bảo rằng số lượng thành phần liên thông không vượt quá $i$ trong bất kỳ trường hợp nào, hãy in ra "-1".
Ví dụ
Dữ liệu vào 1
4 3 3 1 1 2 1 2 3 1 1 3 4 3 1 2 3 2 1 2 1 3 1 3 4 6 2 3 1 2 3 4 5 6 2 2 3 4 5 4 2 1 2 3 2 1 3 1 2
Dữ liệu ra 1
2 1 0 2 1 1 0 2 2 1 1 1 0 -1 1 1 0