题目描述

给出 $N$ 个点的树和 $K$，问能否把树划分成 $\frac{N}{K}$ 个连通块，且每个连通块的点数都是 $K$。

输入格式

第一行，一个整数 $T$，表示数据组数。接下来 $T$ 组数据，对于每组数据：

第一行，两个整数 $N, K$。

接下来 $N - 1$ 行，每行两个整数 $A_i, B_i$，表示边 $(A_i, B_i)$。点用 $1, 2, \ldots, N$ 编号。

输出格式

对于每组数据，输出 YES 或 NO。

输入输出样例

2
4 2
1 2
2 3
3 4
4 2
1 2
1 3
1 4

YES
NO

说明/提示

• 对于 $60 \%$ 的数据，$1 \le N, K \le 10^3$；
• 对于 $100 \%$ 的数据，$1 \le T \le 10$，$1 \le N ,K \le 10^5$。

4
3 1
1 2
2 3
9 1
1 2
1 3
2 4
2 5
1 6
4 7
7 8
7 9
11 8
1 2
2 3
2 4
1 5
3 6
5 7
4 8
2 9
5 10
3 11
18 5
1 2
1 3
1 4
1 5
3 6
1 7
2 8
4 9
6 10
10 11
7 12
11 13
4 14
1 15
3 16
15 17
4 18

YES
YES
NO
NO

3
8 5
1 2
2 3
1 4
1 5
3 6
5 7
2 8
3 3
1 2
2 3
31 24
1 2
1 3
2 4
3 5
2 6
4 7
1 8
4 9
4 10
3 11
3 12
8 13
13 14
7 15
10 16
1 17
11 18
8 19
9 20
20 21
10 22
12 23
18 24
21 25
3 26
20 27
25 28
13 29
12 30
18 31

NO
YES
NO