题目描述

给定一张 \(n\) 个点 \(m\) 条边的无向图，无重边自环。图上的边被染成了黑白两种颜色。

请你求出，有多少组不同的整数 \(\left(b, w\right)\)，满足以下条件:

这张图存在一棵生成树，其恰好有 \(b\) 条黑色的边， \(w\) 条白色的边。

输入格式

第一行输入一个整数 \(T\)，表示数据组数。

对于接下来的每组数据：

第一行输入两个整数 \(n, m\)，表示图的点数和边数.

接下来 \(m\) 行，每行输入三个整数 \(u_i, v_i, w_i\)，表示第 \(i\) 条边连接的两个节点和这条边的颜色。

• \(1 \le n \le 10^5, 1 \le m \le 2 \times 10^5\)
• \(1 \le u_i, v_i \le n\)
• \(u_i \not = v_i\)
• \(\forall i \not = j, \{u_i, v_i\} \not = \{u_j, v_j\}\)
• \(w_i \in \{0, 1\}\)

其中， \(0, 1\) 分别对应黑白两种颜色。

对于单个测试点中的所有数据，保证 \(n\) 总和不超过 \(1.1 \times 10^6\)， \(m\) 总和不超过 \(2.1 \times 10^6\).

输出格式

对于每组数据：

输出一行一个整数表示答案。

样例输入

3
4 6
1 2 0
1 3 1
1 4 0
2 3 0
2 4 1
3 4 0
6 5
1 2 0
2 3 0
3 4 0
4 1 1
5 6 1
10 20
5 9 0
4 8 1
9 10 0
9 2 1
3 5 0
7 2 1
10 8 1
3 9 1
7 4 1
9 1 1
10 6 1
4 6 1
1 8 0
6 8 1
8 7 1
4 2 0
5 10 0
9 8 0
7 10 0
7 5 0

样例输出

3
0
7