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