题目描述

考虑一棵无根树 $T$——这里所说的树并非生物学意义上的树木或植物，而是图论中作为无向图的一种树，含有 $n$ 个节点，节点编号从 $1$ 到 $n$。若你无法理解此处树的定义，请略过此题。

现在我们决定用 $k$ 种不同的颜色对树的节点进行染色，颜色编号从 $1$ 到 $k$。接着，对于每一种颜色 $i = 1, 2, \cdots, k$，定义 $E_i$ 为连接着有颜色 $i$ 的全部节点的最小边子集。若树上没有节点被染上某种指定的颜色 $i$，则 $E_i$ 将为空集。

请尝试确定一种染色方案，使得 $E_1 \cap E_2 \cap \cdots \cap E_k$ 的大小最大化，并输出其大小。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 1000$），表示测试用例的总数。

对于每组测试用例，第一行包含两个正整数 $n$ 表示树的规模，以及 $k$（$k \le 500$）表示颜色的数目。接下来的 $n - 1$ 行中，每行包含两个整数 $x$ 和 $y$，描述树中的一条边。保证给定的图是一棵树。

输入中所有测试用例的 $n$ 之和不超过 $200000$。

输出格式

对于每组测试用例，输出 $E_1 \cap E_2 \cap \cdots \cap E_k$ 的最大可能大小。

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
0
1

提示

翻译由 DeepSeek V3.2 完成