树是一种无向连通图,其中没有循环。这个问题是关于无根树的。树的叶子是最多连接到一个顶点的顶点。
园丁 Vitaly 从 $$$n$$$ 个顶点种了一棵树。他决定修剪这棵树。为此,他执行了许多操作。在一次手术中,他除去了树上的所有叶子。
树的示例。
例如,考虑上图所示的树。下图显示了对树仅应用一项操作的结果。
对树应用“删除所有叶子”操作的结果。
注意操作的特殊情况:
- 对空树($$$0$$$ 顶点)应用操作不会改变它;
- 对一个顶点的树应用操作会删除该顶点(该顶点被视为叶子);
- 对两个顶点的树应用操作会删除两个顶点(两个顶点都被视为叶子)。
Vitaly 按顺序对树应用 $$$k$$$ 操作。还剩下多少个顶点?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例前面都有一个空行。
每个测试用例由几行组成。测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 4 \cdot 10^5$$$, $$$1 \le k \le 2 \cdot 10^5$$$) — 分别是树中的顶点数和操作数。然后是 $$$n - 1$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$),它们描述由边连接的一对顶点。保证给定的图是一棵树并且没有循环或多重边。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$4 \cdot 10^5$$$。
输出
对于每个测试用例在单独的行上输出一个整数 - 应用 $$$k$$$ 操作后保留在树中的顶点数。
示例
输入 #1
6 14 1 1 2 2 3 2 4 4 5 4 6 2 7 7 8 8 9 8 10 3 11 3 12 1 13 13 14 2 200000 1 2 3 2 1 2 2 3 5 1 5 1 3 2 2 1 5 4 6 2 5 1 2 5 5 6 4 2 3 4 7 1 4 3 5 1 1 3 6 1 1 7 2 1
输出 #1
7 0 0 3 1 2
注意
声明中考虑第一个测试用例。
第二个测试用例包含一个有两个顶点的树。 $$$200000$$$ 操作被应用到它。第一个操作删除所有两个顶点,其他操作不会更改树。
在第三个测试用例中,给出了具有三个顶点的树。第一个操作的结果是,只剩下 $$$1$$$ 顶点(索引为 $$$2$$$),第二个操作使树为空。