Universal Cup Judging System

Universal Cup

Limite de temps : 3.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.