[SCOI2005]王室联邦

“余”人国的国王想重新规划自己的国家。他希望将国家划分为若干个省，并由王室联邦的成员分别管理。

这个国家共有 $N$ 个城市，编号为 $1$ 到 $N$。城市之间由道路连接，任意两个不同的城市之间都存在且仅存在一条直接或间接的路径。

为了避免管理过于分散，每个省至少需要包含 $B$ 个城市；为了保证管理效率，每个省至多包含 $3B$ 个城市。

每个省都必须指定一个省会。省会可以位于该省内，也可以位于该省外。对于该省的任意一个城市，从该城市到省会的路径上，除终点省会外的所有城市都必须属于该省。一个城市可以同时作为多个省的省会。

请构造一种满足上述要求的划分方案。如果存在多种方案，输出任意一种即可。

输入格式

第一行包含两个整数 $N$ 和 $B$。

接下来 $N-1$ 行，每行包含两个整数，表示一条道路所连接的两个城市编号。

输出格式

如果无法满足要求，输出一行一个整数 $0$。

否则，第一行输出一个整数 $K$，表示划分出的省的数量，各省编号为 $1$ 到 $K$。

第二行输出 $N$ 个整数，其中第 $I$ 个整数表示编号为 $I$ 的城市所属省的编号。

第三行输出 $K$ 个整数，其中第 $I$ 个整数表示编号为 $I$ 的省的省会城市编号。

样例输入

8 2
1 2
2 3
1 8
8 7
8 6
4 6
6 5

样例输出

2
2 2 2 1 1 2 2 2
6 1

数据范围

• $1\le N\le 1000$；
• $1\le B\le N$。

来源与许可

本题为 SCOI 2005 试题「王室联邦」，题面与测试数据整理自 BZOJ。

样例 1

输入

8 2
1 2
2 3
1 8
8 7
8 6
4 6
6 5

输出

2
2 2 2 1 1 2 2 2
6 1