Tajian løser følgende oppgave:
Gitt en graf med $n$ punkter, har den opprinnelige grafen ingen kanter. Tajian har noen kanter som kan legges til i grafen, og han har delt disse kantene inn i $k$ grupper, der den $i$-te gruppen inneholder $c_i$ kanter. For hver $x \in [1, n]$ ønsker Tajian å vite det minimale antallet kantgrupper han må velge fra disse $k$ gruppene for å legge til i grafen, slik at han er sikker på at antallet sammenhengende komponenter i grafen ikke overstiger $x$.
Selv om det ikke er umiddelbart åpenbart, finnes det artikler som viser at det minimale fargeleggingstallet til et utspennende tre er et NPC-problem. Tajian vet imidlertid ikke dette, så han vil at du skal hjelpe ham med å løse denne oppgaven.
Inndata
Et enkelt testtilfelle inneholder flere datasett.
Den første linjen i inndataene er antall datasett $T$ ($1 \le T \le 10^3$), som representerer antall datasett i dette testtilfellet.
For hvert datasett inneholder den første linjen to heltall $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), som representerer antall punkter og antall kantgrupper.
Den neste delen beskriver informasjonen for de $k$ kantgruppene. For den $i$-te kantgruppen inneholder den første linjen et heltall $c_i$ ($1 \le c_i \le 200$), som representerer antall kanter i denne gruppen. De påfølgende $c_i$ linjene inneholder hver to heltall $u, v$ ($1 \le u, v \le n, u \neq v$), som representerer en kant i denne gruppen.
For et enkelt datasett er det garantert at $\sum c_i \le 200$. For alle data samlet er det garantert at $\sum 2^n \le 2^{16}$.
Utdata
For hvert datasett skal du skrive ut en linje med $n$ heltall, der det $i$-te heltallet representerer svaret når $x = i$.
Hvis det under enhver omstendighet er umulig å sikre at antallet sammenhengende komponenter ikke overstiger $i$, skriv ut "-1".
Eksempler
Inndata 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