【题目描述】

欧艾大陆由 n 个城市组成，呈树形结构。每一个城市就是一个树上的顶点，由无向边相连。

为了方便管理，国王 𝐶rying 希望能够将欧艾大陆的城市分成若干个省，使得每个城市都恰好在一个省内。

𝐶rying 是一个理智的人，经过精密的统计和计算，他认为每个省应该满足以下条件：

• 不能包含太多或太少的城市：即大小应该在 [𝐵, 3 ×𝐵] 内，其中 𝐵 是一个给定的参数。
• 需要指定一个城市作为这个省的省会，与地球人的常识不同，这个省的省会可以不属于这个省，且一个城市可以作为多个省的省会，但是对于每个城市 𝑥，如果该城市所属于的省的省会是 y，那么 (𝑥,y) 之间的简单路径上的所有点都要满足和 𝑥 在同一个省。

你作为国王的首席智囊团，需要帮助他找到一组满足条件的划分方法。 如果有多组划分方案，只需要其中一组即可。

数据保证存在至少一种划分方案。

【输入格式】

第一行两个正整数n,𝐵，表示城市的总数和对省份大小的限制。

接下来 n −1 行，每行两个正整数 𝑥,y，描述一条边。

【输出格式】

第一行一个正整数𝑘，表示将图划分成的省的个数。

第二行n 个数 𝑎1 ,𝑎2 , … ,𝑎𝑛 ，𝑎𝑖 表示第 i个城市属于哪一个省。

第三行 𝑘 个数 𝑏1 ,𝑏2 , … ,𝑏𝑘，𝑏𝑖表示第 i 个省的省会城市。 请保证 𝑘 ≤ n，可以证明，必然存在一种 𝑘 ≤ n 的划分方案。

【样例1 输入】

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

【样例1 输出】

3 
2 1 1 3 3 3 3 2 
2 1 8 

【数据范围】

对于 40% 的数据，n ≤100。

对于 100% 的数据，1≤ 𝐵 ≤ n ≤10000，保证给定的图是一棵树。