Background

滑稽树上滑稽果
滑稽树下你和我
滑稽树前做游戏
滑稽树后做交易

Description

A和B看到滑稽树，有感而发，于是做起了游戏。
游戏规则是这样的：
首先给定一个无向连通图，边权是0或者1。
然后B选择这张图的其中一棵生成树，A的目的是要通过尽量少的步数，猜出这个生成树边的总权值。
每次A猜测一个数，如果刚好猜对，那么B会告诉A猜对了，否则就会告诉A这个数是大了还是小了。
A想知道在最坏情况下需要几步猜出。

Format

Input

第一行一个整数T，表示数据组数(T<=10)。
接下来T组数据，每组数据构成如下：
第一行两个整数n,m(2<=n<=100000,n-1<=m<=200000)，表示所给连通无向图的点数和边数。
接下来m行每行三个整数s,t,w(1<=s,t<=n,0<=w<=1)，表示一条边起终点是s,t，权值为w。

Output

按照输入顺序，对于每一组数据，输出对应的最小步数。

Sample 1

Input

1
2 1
1 2 0

Output

0

Limitation

1s, 512MB for each test case.

Source

wbs