唯一的最小生成树(The Unique MST)

题目描述

本题对应 POJ 1679：The Unique MST。

给定一个包含 $n$ 个顶点和 $m$ 条带权边的连通无向图，请你判断该图的最小生成树（MST）是否唯一。

如果最小生成树唯一，输出最小生成树的边权之和；如果不唯一，输出 Not Unique!。

输入格式

第一行包含一个正整数 $t$（$1 \le t \le 20$），表示测试数据组数。

每组测试数据的第一行包含两个整数 $n, m$（$1 \le n \le 100$），分别表示顶点数与边数；接下来 $m$ 行，每行包含三个正整数 $u, v, w$，表示一条边权为 $w$ 的无向边。保证无重边且图连通。

输出格式

对于每组测试数据，若最小生成树唯一则输出一行一个整数表示其权值和，否则输出一行 Not Unique!。

样例输入 #1

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

样例输出 #1

3
Not Unique!

数据范围

对于 $100\%$ 的数据，$1 \le t \le 20$，$1 \le n \le 100$，$n - 1 \le m \le \frac{n(n-1)}{2}$，$1 \le w \le 10^5$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1500。

测试点分布

出处：原题链接