Colorful
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小A最近学习了最小生成树的算法，觉得非常神奇。
他现在在研究一个更加神奇的问题
给定个点条边的无向图，每条边都有一个颜色，请找到一棵生成树，满足颜色的种类尽量少
保证图联通

输入描述:

第一行数据组数
对于每一组数据，第一行，分别代表点数，边数，颜色种类数量
接下来行，每行三个整数，代表一条边和它的颜色

输出描述:

对于每组数据输出一行一个整数表示答案
示例1

输入

复制 
1
3 3 2
1 2 1
2 3 1
1 3 2

输出

复制 
1

说明

选择边({1,2})和{(2,3)}
示例2

输入

复制 
1
6 8 4
1 2 1
2 3 2
3 4 3
3 5 4
5 6 2
4 6 1
3 5 2
1 3 4

输出

复制 
2

备注:

对于的数据，
对于的数据， , 
对于另外的数据，,,
对于的数据，,, , 
可能有重边，保证没有自环