Tajian sedang menyelesaikan persoalan berikut:
Diberikan sebuah graf dengan $n$ titik, graf awal tidak memiliki sisi. Tajian memiliki beberapa sisi untuk ditambahkan ke dalam graf, dan ia telah membagi sisi-sisi ini ke dalam $k$ kelompok, di mana kelompok ke-$i$ berisi $c_i$ sisi. Untuk setiap $x \in [1, n]$, Tajian ingin mengetahui jumlah kelompok sisi minimum yang perlu ia pilih dari $k$ kelompok tersebut untuk ditambahkan ke dalam graf guna memastikan bahwa banyaknya komponen terhubung di dalam graf tidak melebihi $x$.
Meskipun tidak langsung terlihat jelas, terdapat makalah yang menunjukkan bahwa bilangan pewarnaan minimum dari pohon merentang (spanning tree) adalah persoalan NPC. Namun, Tajian tidak mengetahui hal ini, sehingga ia ingin Anda membantunya menyelesaikan persoalan ini.
Masukan
Satu kasus uji berisi beberapa set data (data set).
Baris pertama masukan adalah banyaknya set data $T$ ($1 \le T \le 10^3$), yang menyatakan banyaknya set data dalam kasus uji ini.
Untuk setiap set data, baris pertama berisi dua bilangan bulat $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), yang menyatakan banyaknya titik dan banyaknya kelompok sisi.
Bagian berikutnya mendeskripsikan informasi untuk $k$ kelompok sisi. Untuk kelompok sisi ke-$i$, baris pertama berisi sebuah bilangan bulat $c_i$ ($1 \le c_i \le 200$), yang menyatakan banyaknya sisi dalam kelompok ini. $c_i$ baris berikutnya masing-masing berisi dua bilangan bulat $u, v$ ($1 \le u, v \le n, u \neq v$), yang menyatakan sebuah sisi dalam kelompok ini.
Untuk satu set data, dijamin bahwa $\sum c_i \le 200$. Untuk seluruh data, dijamin bahwa $\sum 2^n \le 2^{16}$.
Keluaran
Untuk setiap set data, keluarkan satu baris berisi $n$ bilangan bulat, di mana bilangan bulat ke-$i$ menyatakan jawaban ketika $x = i$.
Jika tidak mungkin memastikan bahwa banyaknya komponen terhubung tidak melebihi $i$ dalam keadaan apa pun, keluarkan "-1".
Contoh
Masukan 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
Keluaran 1
2 1 0 2 1 1 0 2 2 1 1 1 0 -1 1 1 0