提示: 欢迎访问OurACM平台。
Problem 2087 统计树边

Accept: 226    Submit: 704
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

在图论中,树:任意两个顶点间有且只有一条路径的图。

生成树:包含了图中所有顶点的一种树。

最小生成树:对于连通的带权图(连通网)G,其生成树也是带权的。生成树T各边的权值总和称为该树的权,权最小的生成树称为G的最小生成树(Minimum Spanning Tree)。最小生成树可简记为MST。

但是,对于一个图而言,最小生成树并不是唯一的。

现在,给你一个连通的有权无向图,图中不包含有自环和重边,你的任务就是寻找出有多少条边,它至少在一个最小生成树里。图保证连通。

Input

输入数据第一行包含一个整数T,表示测试数据的组数。对于每组测试数据:

第一行包含两个整数n,m(1<n<100000,n-1<m<100000),接下来m行,每行三个整数a,b,v(1<=a,b<=n,1<v<500),表示第i条路线连接景点A和景点B,距离是V。两个数字之间用空格隔开。

Output

对于每组测试数据,输出一行,包含一个整数,表示满足条件的边的个数。

Sample Input

1 4 5 1 2 101 1 3 100 2 3 2 2 4 2 3 4 1

Sample Output

4

Source

福州大学第九届程序设计竞赛

Submit  Back  Status  Discuss