Province Partitioning

The King of the "Yu" people wants to reorganize his kingdom by dividing it into several provinces. There are \(N\) cities numbered from 1 to \(N\) and exactly \(N-1\) roads connecting them such that there is a unique (direct or indirect) road between every pair of different cities (i.e. the cities form a tree).

Each province must satisfy the following conditions:

• It contains at least \(B\) cities and at most \(3\times B\) cities. (i.e. if \(S\) is the number of cities in a province then \(B \le S \le 3B\))
• There must be a designated capital for the province. The capital can be chosen from any city (even one not in the province). However, for every city in the province, consider the unique simple path from that city to the designated capital. All cities on this path except the capital must belong to the province.

Note that if the capital is chosen from within the province then the connectivity condition is automatically satisfied. In other words, a valid province is a connected subset of cities with size between \(B\) and \(3B\) (inclusive), and a capital can be any city in that province.

Your task is to help the king partition his kingdom into provinces satisfying the above conditions. If a valid partition exists, output one valid partition; otherwise, output -1.

inputFormat

The input is given in the following format:

N B
u1 v1
u2 v2
... 
 u(N-1) v(N-1)

Here, \(N\) and \(B\) are integers. Next, each of the \(N-1\) lines contains two integers \(u_i\) and \(v_i\) (\(1 \le u_i,v_i \le N\)) indicating that there is a road connecting the cities \(u_i\) and \(v_i\).

It is guaranteed that the cities and roads form a tree.

outputFormat

If a valid partition exists, output it in the following format:

k
p1 p2 ... pN
c1 c2 ... ck

where k is the number of provinces, p_i (for \(1 \le i \le N\)) is the province number (an integer from 1 to k) assigned to city i, and c_j (for \(1 \le j \le k\)) is the chosen capital for the j-th province (note that the capital is chosen from within the province). If more than one valid partition exists, output any one.

If no valid partition exists, simply output -1.

Note: A trivial solution is to output the entire kingdom as one province if \(N\) satisfies \(B \le N \le 3B\); otherwise, output -1. For the purpose of this problem and the given test cases, you may assume that either the entire kingdom is a valid province or no valid partition exists.

sample

5 2
1 2
1 3
3 4
3 5

1
1 1 1 1 1
1

</p>