#include <bits/stdc++.h>
#define rep(_i, _j) for(int _i = 1; _i <= _j; ++_i)
const int inf = 0x3f3f3f3f;
typedef long long LL;
typedef double DB;
using namespace std;
const int maxn = 10000 + 100;
int n, b, k;
int color[maxn], fa[maxn], size[maxn];
vector<int> to[maxn];
vector<pair<int, int> > headquater;
stack<int> subtree;
void dfs(int u) {
int cnt = 0;
subtree.push(u);
for(size_t i = 0; i < to[u].size(); ++i) {
if(to[u][i] != fa[u]) {
fa[to[u][i]] = u;
dfs(to[u][i]);
cnt += size[to[u][i]];
if(cnt < b) {
continue;
} else {
++k;
headquater.push_back(make_pair(u, cnt));
while(subtree.top() != u) {
color[subtree.top()] = k;
subtree.pop();
}
cnt = 0;
}
}
}
size[u] = 1 + cnt;
}
int main() {
scanf("%d%d", &n, &b);
for(int i = 1; i < n; ++i) {
int u, v;
scanf("%d%d", &u, &v);
to[u].push_back(v);
to[v].push_back(u);
}
fa[1] = 0;
dfs(1);
if(n < b) {
puts("0");
} else if(n <= 3 * b) {
puts("1");
for(int i = 1; i <= n; ++i) {
printf("%d ", 1);
}
puts("");
puts("1");
} else {
for(int i = 1; i <= n; ++i) {
if(color[i] == 0) {
color[i] = k;
++headquater[k - 1].second;
}
}
for(size_t i = 0; i < headquater.size(); ++i) {
if(headquater[i].second < b || b * 3 < headquater[i].second) {
puts("0");
return 0;
}
}
printf("%d\n", k);
for(int i = 1; i <= n; ++i) {
printf("%d ", color[i]);
}
puts("");
for(size_t i = 0; i < headquater.size(); ++i) {
printf("%d ", headquater[i].first);
}
puts("");
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgcmVwKF9pLCBfaikgZm9yKGludCBfaSA9IDE7IF9pIDw9IF9qOyArK19pKQpjb25zdCBpbnQgaW5mID0gMHgzZjNmM2YzZjsKdHlwZWRlZiBsb25nIGxvbmcgTEw7CnR5cGVkZWYgZG91YmxlIERCOwp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IG1heG4gPSAxMDAwMCArIDEwMDsKaW50IG4sIGIsIGs7CmludCBjb2xvclttYXhuXSwgZmFbbWF4bl0sIHNpemVbbWF4bl07CnZlY3RvcjxpbnQ+IHRvW21heG5dOwp2ZWN0b3I8cGFpcjxpbnQsIGludD4gPiBoZWFkcXVhdGVyOwpzdGFjazxpbnQ+IHN1YnRyZWU7CnZvaWQgZGZzKGludCB1KSB7CglpbnQgY250ID0gMDsKCXN1YnRyZWUucHVzaCh1KTsKCWZvcihzaXplX3QgaSA9IDA7IGkgPCB0b1t1XS5zaXplKCk7ICsraSkgewoJCWlmKHRvW3VdW2ldICE9IGZhW3VdKSB7CgkJCWZhW3RvW3VdW2ldXSA9IHU7CgkJCWRmcyh0b1t1XVtpXSk7CgkJCWNudCArPSBzaXplW3RvW3VdW2ldXTsKCQkJaWYoY250IDwgYikgewoJCQkJY29udGludWU7CgkJCX0gZWxzZSB7CgkJCQkrK2s7CgkJCQloZWFkcXVhdGVyLnB1c2hfYmFjayhtYWtlX3BhaXIodSwgY250KSk7CgkJCQl3aGlsZShzdWJ0cmVlLnRvcCgpICE9IHUpIHsKCQkJCQljb2xvcltzdWJ0cmVlLnRvcCgpXSA9IGs7CgkJCQkJc3VidHJlZS5wb3AoKTsKCQkJCX0KCQkJCWNudCA9IDA7CgkJCX0KCQl9Cgl9CglzaXplW3VdID0gMSArIGNudDsKfQoKaW50IG1haW4oKSB7CglzY2FuZigiJWQlZCIsICZuLCAmYik7Cglmb3IoaW50IGkgPSAxOyBpIDwgbjsgKytpKSB7CgkJaW50IHUsIHY7CgkJc2NhbmYoIiVkJWQiLCAmdSwgJnYpOwoJCXRvW3VdLnB1c2hfYmFjayh2KTsKCQl0b1t2XS5wdXNoX2JhY2sodSk7Cgl9CglmYVsxXSA9IDA7CglkZnMoMSk7CglpZihuIDwgYikgewoJCXB1dHMoIjAiKTsKCX0gZWxzZSBpZihuIDw9IDMgKiBiKSB7CgkJcHV0cygiMSIpOwoJCWZvcihpbnQgaSA9IDE7IGkgPD0gbjsgKytpKSB7CgkJCXByaW50ZigiJWQgIiwgMSk7CgkJfQoJCXB1dHMoIiIpOwoJCXB1dHMoIjEiKTsKCX0gZWxzZSB7CgkJZm9yKGludCBpID0gMTsgaSA8PSBuOyArK2kpIHsKCQkJaWYoY29sb3JbaV0gPT0gMCkgewoJCQkJY29sb3JbaV0gPSBrOwoJCQkJKytoZWFkcXVhdGVyW2sgLSAxXS5zZWNvbmQ7CgkJCX0KCQl9CgkJZm9yKHNpemVfdCBpID0gMDsgaSA8IGhlYWRxdWF0ZXIuc2l6ZSgpOyArK2kpIHsKCQkJaWYoaGVhZHF1YXRlcltpXS5zZWNvbmQgPCBiIHx8IGIgKiAzIDwgaGVhZHF1YXRlcltpXS5zZWNvbmQpIHsKCQkJCXB1dHMoIjAiKTsKCQkJCXJldHVybiAwOwoJCQl9CgkJfQoJCXByaW50ZigiJWRcbiIsIGspOwoJCWZvcihpbnQgaSA9IDE7IGkgPD0gbjsgKytpKSB7CgkJCXByaW50ZigiJWQgIiwgY29sb3JbaV0pOwoJCX0KCQlwdXRzKCIiKTsKCQlmb3Ioc2l6ZV90IGkgPSAwOyBpIDwgaGVhZHF1YXRlci5zaXplKCk7ICsraSkgewoJCQlwcmludGYoIiVkICIsIGhlYWRxdWF0ZXJbaV0uZmlyc3QpOwoJCX0KCQlwdXRzKCIiKTsKCX0KCgoJcmV0dXJuIDA7Cn0K