Universal Cup Judging System

Universal Cup

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

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

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.