M. Vassals
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

After conquering many cities, the king of Nlogonia has decided to reward his vassals for their loyalty and success in battle. The conquered territory consists of $$$n$$$ cities connected by bidirectional roads. He wants to divide it among $$$v$$$ vassals so that each vassal controls at least one city and each city is controlled by exactly one vassal.

However, the vassals are quick-tempered and will seize any excuse to quarrel. To keep the peace, the king imposes a rule: each city may have at most one road leading to a city controlled by a different vassal.

Fortunately, the cities form a tree: there is exactly one path between any pair of cities, and there are no road cycles.

The king is busy with his royal duties and has asked you, the finest programmer in Nlogonia, to determine whether such a division is possible. If it is, also provide a valid assignment of cities.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 5 \times 10^{4}$$$), the number of test cases.

The first line of each test case contains two integers $$$n$$$ ($$$2 \le n \le 3 \times 10^{5}$$$) and $$$v$$$ ($$$1 \le v \le n$$$), the numbers of cities and vassals.

Each of the next $$$n-1$$$ lines contains two distinct integers $$$a$$$ and $$$b$$$ ($$$1 \leq a,b \leq n$$$), indicating a bidirectional road between cities $$$a$$$ and $$$b$$$. The roads are guaranteed to form a tree.

The sum of $$$n$$$ over all test cases does not exceed $$$500000$$$.

Output

Answer the test cases in input order.

If no valid division exists, print NAO (Portuguese for "no").

Otherwise, print SIM ("yes") on the first line. On the second line, print $$$n$$$ integers $$$c_1,c_2,\ldots,c_n$$$, where $$$c_i$$$ ($$$1 \leq c_i \leq v$$$) is the vassal controlling city $$$i$$$. Every vassal must control at least one city. If several valid assignments exist, print any of them.

Example
Input
2
8 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
12 3
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
Output
SIM
1 2 2 3 3 3 3 3
NAO