#P17902. Challenge NPC II
Challenge NPC II
一个无向图有 个顶点,初始没有边。给定 组边,第 组包含 条边。
可以选择若干组,将所选组内的所有边同时加入图中。对每个 ,分别求使图的连通分量数不超过 所需选择的最少组数。若无法做到,答案为 。
每个 独立求最优值,可以选空集;重复出现的边不会改变连通性的含义。
输入格式
第一行给出测试组数 ,。
每组测试先给出 ,,。
随后依次描述 组边:先给出 ,再给出 行端点 。其中 ,,。
每组测试满足 。一个输入文件的所有测试组满足 。
输出格式
每组测试输出一行 个整数,第 个整数就是连通分量数不超过 时的答案。
样例 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