P2325 [SCOI2005] 王室联邦

“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。 他的国家有 $N$ 个城市，编号为 $1\ldots N$。 一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。 为了防止管理太过分散，每个省至少要有 $B$ 个城市。 为了能有效的管理，每个省最多只有 $3\times B$ 个城市。 每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。 但是该省的任意一个城市到达省会所经过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。 一个城市可以作为多个省的省会。 聪明的你快帮帮这个国王吧！

无

无

对于 $100\%$ 的数据，$1\le B\leq N\le 10^3$。 感谢 @[FlierKing](/user/9433) 提供 spj。