P2325 [SCOI2005] Royal Federation

The king of the country of the “Yu” people (Yu) plans to reorganize his nation. He wants to divide the country into several provinces, each governed by a member of their royal federation. There are $N$ cities, numbered $1\ldots N$. Some cities are connected by roads. Between any two distinct cities, there is exactly one simple path (direct or indirect). To avoid overly fragmented management, each province must contain at least $B$ cities. For effective governance, each province may contain at most $3\times B$ cities. Each province must have a capital. The capital may be located inside the province or outside it. However, for any city in the province, all cities on the path to the capital (except the last city, i.e., the capital itself) must belong to that province. A city may serve as the capital for multiple provinces. Please help the king.

The first line contains two integers $N,B$. The next $N-1$ lines each describe an edge, with two integers giving the indices of the two cities connected by this road.

If it is impossible to satisfy the king’s requirements, output $0$. Otherwise, on the first line output an integer $K$, the number of provinces in your partition. On the second line, output $N$ integers. The $I$-th number is the index of the province to which city $I$ belongs. Each index must be in $[1,K]$. On the third line, output $K$ integers, the city indices of the capitals of these $K$ provinces. If multiple solutions exist, you may output any of them.

For $100\%$ of the testdata, $1\le B\leq N\le 10^3$. Thanks to @[FlierKing](/user/9433) for providing the spj. Translated by ChatGPT 5