Tajian 正在解決以下問題:
給定一個含有 $n$ 個點嘅圖,初始時圖入面冇邊。Tajian 有一啲邊需要加落個圖度,佢將呢啲邊分成咗 $k$ 組,其中第 $i$ 組包含 $c_i$ 條邊。對於每個 $x \in [1, n]$,Tajian 想知道,佢最少需要從呢 $k$ 組邊入面揀幾多組邊加落個圖度,先至可以確保圖入面嘅連通分量個數唔超過 $x$。
雖然呢樣嘢唔係一眼就睇得出,但係有論文指出,生成樹嘅最小著色數係一個 NPC 問題。然而,Tajian 並唔知道呢一點,所以佢希望你幫佢解決呢個問題。
輸入格式
單個測試點包含多組測試數據。
輸入嘅第一行係測試數據組數 $T$($1 \le T \le 10^3$),表示呢個測試點入面嘅測試數據組數。
對於每組測試數據,第一行包含兩個整數 $n, k$($2 \le n \le 16, 1 \le k \le 200$),分別表示點嘅數量同埋邊組嘅數量。
跟住落嚟嘅部分描述呢 $k$ 組邊嘅資訊。對於第 $i$ 組邊,第一行包含一個整數 $c_i$($1 \le c_i \le 200$),表示呢組入面嘅邊數。跟住落嚟嘅 $c_i$ 行,每行包含兩個整數 $u, v$($1 \le u, v \le n, u \neq v$),表示呢組入面嘅一條邊。
對於單組測試數據,保證 $\sum c_i \le 200$。對於所有數據,保證 $\sum 2^n \le 2^{16}$。
輸出格式
對於每組測試數據,輸出一行 $n$ 個整數,其中第 $i$ 個整數表示當 $x = i$ 時嘅答案。
如果喺任何情況下都無法確保連通分量個數唔超過 $i$,就輸出 "-1"。
範例
輸入格式 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
輸出格式 1
2 1 0 2 1 1 0 2 2 1 1 1 0 -1 1 1 0