Description
“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成
员来管理。他的国家有n个城市，编号为1..n。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条
直接或间接的道路。为了防止管理太过分散，每个省至少要有B个城市，为了能有效的管理，每个省最多只有3B个
城市。每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省会所经
过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。一个城市可以作为多个省的省会。聪明的
你快帮帮这个国王吧！
Input
第一行包含两个数N，B（1<=N<=1000, 1 <= B <= N）。接下来N－1行，每行描述一条边，包含两个数，即这
条边连接的两个城市的编号。
Output
如果无法满足国王的要求，输出0。否则输出数K，表示你给出的划分方案中省的个数，编号为1..K。第二行输
出N个数，第I个数表示编号为I的城市属于的省的编号，第三行输出K个数，表示这K个省的省会的城市编号，如果
有多种方案，你可以输出任意一种。
Sample Input
8 2
1 2
2 3
1 8
8 7
8 6
4 6
6 5
1 2
2 3
1 8
8 7
8 6
4 6
6 5
Sample Output
3
2 1 1 3 3 3 3 2
2 1 8
2 1 1 3 3 3 3 2
2 1 8
正解：树上分块
解题报告：
这道题只需要随意输出一组方案就可以了，似乎可以乱搞。。。
考虑树上分块，每当扫到发现子树结点已经不小于B了，那么考虑把他们直接划成一个省，并且以当前根结点为省会即可。
并且把子树中所有结点划到一个块中，用栈维护一下就可以了。那么最后会剩下一些结点，随便丢哪个块都是可以的，只要发现路上有一个点已经被划成某个块中，那么把接下来的子树中的点也都划成这个块即可，这样才能保证题目要求。
//It is made by jump~
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#ifdef WIN32
#define OT "%I64d"
#else
#define OT "%lld"
#endif
using namespace std;
typedef long long LL;
const int MAXN = ;
int first[MAXN],to[MAXN*],next[MAXN*],size[MAXN];
int n,k,ecnt,B,cnt;
int que[MAXN],top;
int cap[MAXN];
int belong[MAXN]; inline int getint()
{
int w=,q=;
char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar();
if (c=='-') q=, c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar();
return q ? -w : w;
} inline void dfs(int x,int fa){
que[++top]=x;
for(int i=first[x];i;i=next[i]) {
int v=to[i];
if(v==fa) continue;
dfs(v,x);
if(size[x]+size[v]>=B) {//子树超过范围
cap[++k]=x;//直接以子树为省，根为省会
while(que[top]!=x) belong[que[top--]]=k;
size[x]=;
}else size[x]+=size[v];
}
size[x]++;
} inline void paint(int x,int fa,int col){//剩下的随便放
if(!belong[x]) belong[x]=col;
else col=belong[x];//练到当前块下
for(int i=first[x];i;i=next[i]) {
if(to[i]!=fa) paint(to[i],x,col);
}
} inline void work(){
n=getint(); B=getint(); int x,y;
for(int i=;i<n;i++) {
x=getint(); y=getint();
next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y;
next[++ecnt]=first[y]; first[y]=ecnt; to[ecnt]=x;
}
dfs(,);
if(!k) cap[++k]=;
paint(x,,k);
printf("%d\n",k);
for(int i=;i<=n;i++) printf("%d ",belong[i]);printf("\n");
for(int i=;i<=k;i++) printf("%d ",cap[i]);
} int main()
{
work();
return ;
}