Tajian löser följande problem:
Givet en graf med $n$ punkter har den ursprungliga grafen inga kanter. Tajian har några kanter att lägga till i grafen, och han har delat in dessa kanter i $k$ grupper, där den $i$-te gruppen innehåller $c_i$ kanter. För varje $x \in [1, n]$ vill Tajian veta det minimala antalet kantgrupper han behöver välja bland dessa $k$ grupper att lägga till i grafen för att säkerställa att antalet sammanhängande komponenter i grafen inte överstiger $x$.
Även om det inte är omedelbart uppenbart finns det artiklar som visar att det minimala färgningsantalet för ett uppspännande träd är ett NPC-problem. Tajian vet dock inte detta, så han vill att du hjälper honom att lösa detta problem.
Indata
Ett enskilt testfall innehåller flera datamängder.
Den första raden i indatan är antalet datamängder $T$ ($1 \le T \le 10^3$), vilket representerar antalet datamängder i detta testfall.
För varje datamängd innehåller den första raden två heltal $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), som representerar antalet punkter och antalet kantgrupper.
Nästa avsnitt beskriver informationen för de $k$ kantgrupperna. För den $i$-te kantgruppen innehåller den första raden ett heltal $c_i$ ($1 \le c_i \le 200$), som representerar antalet kanter i denna grupp. De följande $c_i$ raderna innehåller var och en två heltal $u, v$ ($1 \le u, v \le n, u \neq v$), som representerar en kant i denna grupp.
För en enskild datamängd garanteras att $\sum c_i \le 200$. För all data garanteras att $\sum 2^n \le 2^{16}$.
Utdata
För varje datamängd, skriv ut en rad med $n$ heltal, där det $i$-te heltalet representerar svaret när $x = i$.
Om det under inga omständigheter är möjligt att säkerställa att antalet sammanhängande komponenter inte överstiger $i$, skriv ut "-1".
Exempel
Indata 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
Utdata 1
2 1 0 2 1 1 0 2 2 1 1 1 0 -1 1 1 0