#P17902. Challenge NPC II

Challenge NPC II

一个无向图有 nn 个顶点,初始没有边。给定 kk 组边,第 ii 组包含 cic_i 条边。

可以选择若干组,将所选组内的所有边同时加入图中。对每个 x=1,2,…,nx=1,2,\ldots,n,分别求使图的连通分量数不超过 xx 所需选择的最少组数。若无法做到,答案为 −1-1。

每个 xx 独立求最优值,可以选空集;重复出现的边不会改变连通性的含义。

输入格式

第一行给出测试组数 TT,1≤T≤10001\le T\le1000。

每组测试先给出 n,kn,k,2≤n≤162\le n\le16,1≤k≤2001\le k\le200。

随后依次描述 kk 组边:先给出 cic_i,再给出 cic_i 行端点 u,vu,v。其中 1≤ci≤2001\le c_i\le200,1≤u,v≤n1\le u,v\le n,u≠vu\ne v。

每组测试满足 ∑ici≤200\sum_i c_i\le200。一个输入文件的所有测试组满足 ∑2n≤65536\sum 2^n\le65536。

输出格式

每组测试输出一行 nn 个整数,第 xx 个整数就是连通分量数不超过 xx 时的答案。

样例 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

输出

2 1 0
2 1 1 0
2 2 1 1 1 0
-1 1 1 0