树分块。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
struct edge{
	int x,y,pre;
}a[2*N];
int last[N],alen;
void ins(int x,int y){
	a[++alen]=edge{x,y,last[x]};
	last[x]=alen;
}
int n,B;
int top,sta[N],cnt,root[N],bel[N];
void dfs(int x,int fa){
	int now=top;
	for(int k=last[x];k;k=a[k].pre){
		int y=a[k].y;
		if(y==fa)continue;
		dfs(y,x);
		if(top-now>=B){
			root[++cnt]=x;
			while(top>now){
				bel[sta[top--]]=cnt;
			}
		}
	}
	sta[++top]=x;
}
int main(){
	scanf("%d%d",&n,&B);
	alen=1;memset(last,0,sizeof(last));
	for(int i=1;i<n;i++){
		int x,y;scanf("%d%d",&x,&y);
		ins(x,y),ins(y,x);
	}
	dfs(1,0);
	if(cnt==0)root[++cnt]=1;
	while(top>0){
		bel[sta[top--]]=cnt;
	}
	printf("%d\n",cnt);
	for(int i=1;i<=n;i++){
		printf("%d ",bel[i]);
	}
	puts("");
	for(int i=1;i<=cnt;i++){
		printf("%d ",root[i]);
	}
	return 0;
}