[ABC352] E - Clique Connect

E - Clique Connect

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 450 分

题面

给定一个带有 个顶点（编号从 至 ）的带权无向图 。初始时，没有边。

您将执行 次操作以向 添加边。第 次操作（）如下：

• 给定一个顶点子集 ，包含 个顶点。对于集合 中所有 对，其中 且 ，在顶点 和 之间添加权重为 的边。

执行完所有 次操作后，确定 是否是连通的。如果是连通的，则找出 的最小生成树中边的总权重。

限制条件

• 所有输入值均为整数。

---

输入

输入从标准输入给出，格式如下：

输出

如果 在所有 次操作后仍未连通，则输出 -1。如果 连通，则输出 的最小生成树中边的总权重。

---

输入样例 1

4 3
3 3
1 2 3
2 2
1 2
3 4
1 3 4

输出样例 1

9

左图显示了所有 次操作后的 ，右图显示了 的最小生成树（边旁边的数字表示它们的权重）。

最小生成树中边的总权重为 。

---

输入样例 2

3 2
2 1
1 2
2 1
1 2

输出样例 2

-1

即使在所有 次操作后， 仍未连通。

---

输入样例 3

10 5
6 158260522
1 3 6 8 9 10
10 877914575
1 2 3 4 5 6 7 8 9 10
4 602436426
2 6 7 9
6 24979445
2 3 4 5 8 10
4 861648772
2 4 8 9

输出样例 3

1202115217