Universal Cup Judging System

Universal Cup

Time Limit: 3.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

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

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.