J. 画圈
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Djangle 给你一个连通的简单无向图，初始时每条边都有一个颜色：白色或黑色。

每次操作，你可以选择一个包含至少一条白边的简单环，将这个环中所有的边都涂成黑色。请注意，你并不一定需要最终把所有边都变为黑色。

请问，最多可以进行多少次这样的操作？

简单环的定义是：由若干条边首尾连接而成的闭合路径，且其中没有重复的边。

Input

第一行包含一个整数 $$$T(1\le T\le 10^4)$$$，表示数据组数。

接下来每组数据的第一行包含两个整数 $$$n, m(1\le n\le \sum n\le 2\times 10^5,n-1\le m\le \min\{3\times 10^5,\frac{n\times (n-1)}{2}\},\sum m\le 3\times 10^5)$$$，表示图的点数和边数。

接下来 $$$m$$$ 行，每行包含三个整数 $$$u, v, \mathrm{col}(1\le u,v\le n,\mathrm{col}\in\{0,1\})$$$，表示存在一条连接点 $$$u$$$ 和点 $$$v$$$ 的无向边，颜色为 $$$\mathrm{col}$$$。如果 $$$\mathrm{col} = 0$$$，表示该边为白色；否则表示该边为黑色。

保证输入的图没有重边和自环。

Output

对于每组数据，输出一个整数，表示最多可以进行多少次操作。

Example
Input
1
9 10
1 2 1
2 3 0
3 4 1
4 5 0
5 6 1
6 7 0
7 8 1
8 1 0
2 9 0
9 6 1
Output
2
Note

第一次操作简单环 $$$2-9-6-7-8-1-2$$$，第二次操作简单环 $$$1-2-3-4-5-6-7-8-1$$$。

容易证明，不存在其他的操作方案，能够操作 $$$3$$$ 次以上。