Description

Given a tree with $N$ vertices and an integer $K$, determine whether it can be partitioned into $\frac{N}{K}$ connected components, each containing exactly $K$ vertices.

Input Format

The first line contains an integer $T$, the number of test cases. Then follow $T$ test cases:

The first line of each test case contains two integers $N, K$.

The next $N - 1$ lines each contain two integers $A_i, B_i$, denoting the edge $(A_i, B_i)$. The vertices are labeled $1, 2, \ldots, N$.

Output Format

For each test case, output YES or NO.

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

YES
NO

Hint

• For $60\%$ of the testdata, $1 \le N, K \le 10^3$.
• For $100\%$ of the testdata, $1 \le T \le 10$, $1 \le N, K \le 10^5$.

Translated by ChatGPT 5