Problem E: 独特的MST

Problem E: 独特的MST

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 226  Solved: 38
[Submit] [Status] [Web Board] [Creator:]

Description

给定连接的无向图,请问它的最小生成树是否唯一。
定义1(生成树):考虑连通的无向图G =(V,E)。 G'的生成树是G的子图,比如T =(V',E'),具有以下属性:
1. V'= V.
2.T是连接的和非循环的。
定义2(最小生成树):考虑边加权,连通,无向图G =(V,E)。 G的最小生成树T =(V,E')是总成本最小的生成树。 T的总成本是指E'中所有边缘的权重之和。

Input

t为多组输入
第一行包含单个整数t(1 <= t <= 20),即测试用例的数量。每个案例代表一个图表。它以包含两个整数n和m(1 <= n <= 100),节点数和边数的行开始。以下m行中的每一行包含三元组(xi,yi,wi),表示xi和yi通过权重= wi的边连接。

Output

对于每个输入,如果MST是唯一的,则打印它的总成本,否则打印字符串'Not Unique!'。

Sample Input Copy

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

Sample Output Copy

3
Not Unique!