Tajian ratkaisee seuraavaa tehtävää:
Annetaan verkko, jossa on $n$ pistettä; alkuperäisessä verkossa ei ole kaaria. Tajianilla on joukko kaaria verkkoon lisättäväksi, ja hän on jakanut nämä kaaret $k$ ryhmään, missä $i$:s ryhmä sisältää $c_i$ kaarta. Jokaiselle $x \in [1, n]$ Tajian haluaa tietää pienimmän määrän kaariryhmiä, jotka hänen täytyy valita näistä $k$ ryhmästä ja lisätä verkkoon varmistaakseen, että verkon yhtenäisten komponenttien lukumäärä on enintään $x$.
Vaikka se ei ole heti ilmeistä, on olemassa tutkimuksia, jotka osoittavat, että virittävän puun pienin väritysluku on NPC-ongelma. Tajian ei kuitenkaan tiedä tätä, joten hän haluaa sinun auttavan häntä ratkaisemaan tämän tehtävän.
Syöte
Yksi testitapaus sisältää useita testijoukkoja.
Syötteen ensimmäinen rivi on testijoukkojen lukumäärä $T$ ($1 \le T \le 10^3$), joka kertoo testijoukkojen määrän tässä testitapauksessa.
Jokaisen testijoukon ensimmäinen rivi sisältää kaksi kokonaislukua $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), jotka kertovat pisteiden lukumäärän ja kaariryhmien lukumäärän.
Seuraava osio kuvaa tiedot $k$ kaariryhmälle. $i$:nnelle kaariryhmälle ensimmäinen rivi sisältää kokonaisluvun $c_i$ ($1 \le c_i \le 200$), joka kertoo kaarien lukumäärän tässä ryhmässä. Seuraavat $c_i$ riviä sisältävät kukin kaksi kokonaislukua $u, v$ ($1 \le u, v \le n, u \neq v$), jotka kuvaavat yhtä tämän ryhmän kaarta.
Yksittäiselle testijoukolle taataan, että $\sum c_i \le 200$. Kaikille syötteen tiedoille taataan, että $\sum 2^n \le 2^{16}$.
Tuloste
Tulosta jokaiselle testijoukolle rivi, jossa on $n$ kokonaislukua, missä $i$:s kokonaisluku kuvaa vastausta, kun $x = i$.
Jos missään olosuhteissa ei ole mahdollista varmistaa, että yhtenäisten komponenttien lukumäärä on enintään $i$, tulosta "-1".
Esimerkit
Syöte 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
Tuloste 1
2 1 0 2 1 1 0 2 2 1 1 1 0 -1 1 1 0