Tajian löst das folgende Problem:
Gegeben ist ein Graph mit $n$ Punkten; der ursprüngliche Graph hat keine Kanten. Tajian hat einige Kanten, die er zum Graphen hinzufügen möchte, und er hat diese Kanten in $k$ Gruppen unterteilt, wobei die $i$-te Gruppe $c_i$ Kanten enthält. Für jedes $x \in [1, n]$ möchte Tajian wissen, wie viele Kantengruppen er mindestens aus diesen $k$ Gruppen auswählen und zum Graphen hinzufügen muss, um sicherzustellen, dass die Anzahl der Zusammenhangskomponenten im Graphen $x$ nicht überschreitet.
Obwohl es nicht sofort offensichtlich ist, gibt es wissenschaftliche Arbeiten, die zeigen, dass die minimale Färbungszahl eines Spannbaums ein NPC-Problem ist. Tajian weiß dies jedoch nicht und möchte daher, dass du ihm bei der Lösung dieses Problems hilfst.
Eingabe
Ein einzelner Testfall enthält mehrere Datensätze.
Die erste Zeile der Eingabe ist die Anzahl der Datensätze $T$ ($1 \le T \le 10^3$), die die Anzahl der Datensätze in diesem Testfall angibt.
Für jeden Datensatz enthält die erste Zeile zwei ganze Zahlen $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), die die Anzahl der Punkte und die Anzahl der Kantengruppen angeben.
Der nächste Abschnitt beschreibt die Informationen für die $k$ Kantengruppen. Für die $i$-te Kantengruppe enthält die erste Zeile eine ganze Zahl $c_i$ ($1 \le c_i \le 200$), die die Anzahl der Kanten in dieser Gruppe angibt. Die folgenden $c_i$ Zeilen enthalten jeweils zwei ganze Zahlen $u, v$ ($1 \le u, v \le n, u \neq v$), die eine Kante in dieser Gruppe darstellen.
Für einen einzelnen Datensatz wird garantiert, dass $\sum c_i \le 200$ gilt. Für alle Daten zusammen wird garantiert, dass $\sum 2^n \le 2^{16}$ gilt.
Ausgabe
Gib für jeden Datensatz eine Zeile mit $n$ ganzen Zahlen aus, wobei die $i$-te ganze Zahl die Antwort für $x = i$ darstellt.
Falls es unter keinen Umständen möglich ist sicherzustellen, dass die Anzahl der Zusammenhangskomponenten $i$ nicht überschreitet, gib "-1" aus.
Beispiele
Eingabe 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
Ausgabe 1
2 1 0 2 1 1 0 2 2 1 1 1 0 -1 1 1 0