Tajian sta risolvendo il seguente problema:
Dato un grafo con $n$ punti, il grafo iniziale non ha archi. Tajian ha alcuni archi da aggiungere al grafo e li ha divisi in $k$ gruppi, dove l'$i$-esimo gruppo contiene $c_i$ archi. Per ogni $x \in [1, n]$, Tajian vuole sapere il numero minimo di gruppi di archi che deve selezionare da questi $k$ gruppi da aggiungere al grafo per garantire che il numero di componenti connesse nel grafo non superi $x$.
Sebbene non sia immediatamente ovvio, esistono articoli scientifici che indicano che il numero minimo di colorazione di un albero ricoprente è un problema NPC. Tuttavia, Tajian non lo sa, quindi vuole che tu lo aiuti a risolvere questo problema.
Input
Un singolo caso di test contiene più set di dati.
La prima riga di input è il numero di set di dati $T$ ($1 \le T \le 10^3$), che rappresenta il numero di set di dati in questo caso di test.
Per ogni set di dati, la prima riga contiene due interi $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), che rappresentano il numero di punti e il numero di gruppi di archi.
La sezione successiva descrive le informazioni per i $k$ gruppi di archi. Per l'$i$-esimo gruppo di archi, la prima riga contiene un intero $c_i$ ($1 \le c_i \le 200$), che rappresenta il numero di archi in questo gruppo. Le successive $c_i$ righe contengono ciascuna due interi $u, v$ ($1 \le u, v \le n, u \neq v$), che rappresentano un arco in questo gruppo.
Per un singolo set di dati, è garantito che $\sum c_i \le 200$. Per tutti i dati, è garantito che $\sum 2^n \le 2^{16}$.
Output
Per ogni set di dati, stampa una riga di $n$ interi, dove l'$i$-esimo intero rappresenta la risposta quando $x = i$.
Se è impossibile garantire che il numero di componenti connesse non superi $i$ in qualsiasi circostanza, stampa "-1".
Esempi
Input 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
Output 1
2 1 0 2 1 1 0 2 2 1 1 1 0 -1 1 1 0