Tajian er að leysa eftirfarandi verkefni:
Gefið er net með $n$ punktum, upphaflega netið hefur enga leggi. Tajian er með nokkra leggi til að bæta við netið og hann hefur skipt þessum leggjum í $k$ hópa, þar sem $i$-ti hópurinn inniheldur $c_i$ leggi. Fyrir hvert $x \in [1, n]$ vill Tajian vita lágmarksfjölda hópa af leggjum sem hann þarf að velja úr þessum $k$ hópum til að bæta við netið svo tryggt sé að fjöldi samanhangandi þátta í netinu fari ekki yfir $x$.
Þótt það sé ekki augljóst við fyrstu sýn eru til greinar sem benda á að lágmarkslitunartala spannandi trés sé NPC-verkefni. Hins vegar veit Tajian þetta ekki, svo hann vill að þú hjálpir sér að leysa þetta verkefni.
Inntak
Eitt prófunartilvik inniheldur mörg gagnasett.
Fyrsta línan í inntakinu er fjöldi gagnasetta $T$ ($1 \le T \le 10^3$), sem táknar fjölda gagnasetta í þessu prófunartilviki.
Fyrir hvert gagnasett inniheldur fyrsta línan tvær heiltölur $n, k$ ($2 \le n \le 16, 1 \le k \le 200$), sem tákna fjölda punkta og fjölda hópa af leggjum.
Næsti hluti lýsir upplýsingunum fyrir $k$ hópa leggja. Fyrir $i$-ta hóp leggja inniheldur fyrsta línan heiltölu $c_i$ ($1 \le c_i \le 200$), sem táknar fjölda leggja í þessum hópi. Næstu $c_i$ línur innihalda hver um sig tvær heiltölur $u, v$ ($1 \le u, v \le n, u \neq v$), sem tákna legg í þessum hópi.
Fyrir eitt gagnasett er tryggt að $\sum c_i \le 200$. Fyrir öll gögn er tryggt að $\sum 2^n \le 2^{16}$.
Úttak
Fyrir hvert gagnasett skal prenta línu með $n$ heiltölum, þar sem $i$-ta heiltalan táknar svarið þegar $x = i$.
Ef ómögulegt er að tryggja að fjöldi samanhangandi þátta fari ekki yfir $i$ undir nokkrum kringumstæðum skal prenta "-1".
Dæmi
Inntak 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
Úttak 1
2 1 0 2 1 1 0 2 2 1 1 1 0 -1 1 1 0