Tajian résout le problème suivant :
Étant donné un graphe à $n$ sommets, le graphe initial ne contient aucune arête. Tajian a des arêtes à ajouter au graphe, et il a divisé ces arêtes en $k$ groupes, où le $i$-ème groupe contient $c_i$ arêtes. Pour chaque $x \in [1, n]$, Tajian veut connaître le nombre minimal de groupes d'arêtes qu'il doit sélectionner parmi ces $k$ groupes à ajouter au graphe afin de garantir que le nombre de composantes connexes dans le graphe ne dépasse pas $x$.
Bien que cela ne soit pas immédiatement évident, certains articles indiquent que le nombre chromatique minimal d'un arbre couvrant est un problème NPC. Cependant, Tajian l'ignore, il souhaite donc que vous l'aidiez à résoudre ce problème.
Entrée
Un seul cas de test contient plusieurs jeux de données.
La première ligne de l'entrée est le nombre de jeux de données $T$ ($1 \le T \le 10^3$), représentant le nombre de jeux de données dans ce cas de test.
Pour chaque jeu de données, la première ligne contient deux entiers $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), représentant le nombre de sommets et le nombre de groupes d'arêtes.
La section suivante décrit les informations pour les $k$ groupes d'arêtes. Pour le $i$-ème groupe d'arêtes, la première ligne contient un entier $c_i$ ($1 \le c_i \le 200$), représentant le nombre d'arêtes dans ce groupe. Les $c_i$ lignes suivantes contiennent chacune deux entiers $u, v$ ($1 \le u, v \le n, u \neq v$), représentant une arête de ce groupe.
Pour un seul jeu de données, il est garanti que $\sum c_i \le 200$. Pour l'ensemble des données, il est garanti que $\sum 2^n \le 2^{16}$.
Sortie
Pour chaque jeu de données, affichez une ligne de $n$ entiers, où le $i$-ème entier représente la réponse lorsque $x = i$.
S'il est impossible de garantir que le nombre de composantes connexes ne dépasse pas $i$ en toutes circonstances, affichez "-1".
Exemples
Entrée 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
Sortie 1
2 1 0 2 1 1 0 2 2 1 1 1 0 -1 1 1 0