#216951. [ICPC 2017 Shenyang R] Tree

Consider a un-rooted tree which is not the biological significance of tree or plant, but a tree as an undirected graph in graph theory with nodes, labelled from 1 to . If you cannot understand the concept of a tree here, please omit this problem.

Now we decide to colour its nodes with distinct colours, labelled from 1 to . Then for each colour , define as the minimum subset of edges connecting all nodes coloured by . If there is no node of the tree coloured by a specified colour , will be empty.

Try to decide a colour scheme to maximize the size of , and output its size.

The first line of input contains an integer (), indicating the total number of test cases.

For each case, the first line contains two positive integers which is the size of the tree and () which is the number of colours. Each of the following lines contains two integers and describing an edge between them. We are sure that the given graph is a tree.

The summation of in input is smaller than or equal to .

For each test case, output the maximum size of .

样例输入 1

3
4 2
1 2
2 3
3 4
4 2
1 2
1 3
1 4
6 3
1 2
2 3
3 4
3 5
6 2

样例输出 1

1
0
1