Tajian está resolviendo el siguiente problema:
Dado un grafo con $n$ puntos, el grafo inicial no tiene aristas. Tajian tiene algunas aristas para añadir al grafo y ha dividido estas aristas en $k$ grupos, donde el $i$-ésimo grupo contiene $c_i$ aristas. Para cada $x \in [1, n]$, Tajian quiere saber el número mínimo de grupos de aristas que necesita seleccionar de estos $k$ grupos para añadir al grafo con el fin de asegurar que el número de componentes conexas en el grafo no exceda $x$.
Aunque no es evidente a primera vista, existen artículos que indican que el número mínimo de coloración de un árbol generador es un problema NPC. Sin embargo, Tajian no sabe esto, por lo que quiere que le ayudes a resolver este problema.
Entrada
Un solo caso de prueba contiene múltiples conjuntos de datos.
La primera línea de la entrada es el número de conjuntos de datos $T$ ($1 \le T \le 10^3$), que representa el número de conjuntos de datos en este caso de prueba.
Para cada conjunto de datos, la primera línea contiene dos enteros $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), que representan el número de puntos y el número de grupos de aristas.
La siguiente sección describe la información de los $k$ grupos de aristas. Para el $i$-ésimo grupo de aristas, la primera línea contiene un entero $c_i$ ($1 \le c_i \le 200$), que representa el número de aristas en este grupo. Las siguientes $c_i$ líneas contienen cada una dos enteros $u, v$ ($1 \le u, v \le n, u \neq v$), que representan una arista en este grupo.
Para un solo conjunto de datos, se garantiza que $\sum c_i \le 200$. Para todos los datos, se garantiza que $\sum 2^n \le 2^{16}$.
Salida
Para cada conjunto de datos, imprime una línea con $n$ enteros, donde el $i$-ésimo entero representa la respuesta cuando $x = i$.
Si bajo cualquier circunstancia es imposible asegurar que el número de componentes conexas no exceda $i$, imprime "-1".
Ejemplos
Entrada 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
Salida 1
2 1 0 2 1 1 0 2 2 1 1 1 0 -1 1 1 0