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