「SCOI2005」王室联邦
题号：NC208301
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

「余」人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。
他的国家有 个城市，编号为 。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。为了防止管理太过分散，每个省至少要有 个城市，为了能有效的管理，每个省最多只有 个城市。
每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。
一个城市可以作为多个省的省会。
聪明的你快帮帮这个国王吧！

输入描述:

第一行包含两个数  。接下来 N-1 行，每行描述一条边，包含两个数，即这条边连接的两个城市的编号。

输出描述:

如果无法满足国王的要求，输出 。否则第一行输出数  ，表示你给出的划分方案中省的个数，编号为  。第二行输出  个数，第  个数表示编号为  的城市属于的省的编号，第三行输出  个数，表示这 个省的省会的城市编号，如果有多种方案，你可以输出任意一种。
示例1

输入

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

输出

复制 
3 
2 1 1 3 3 3 3 2 
2 1 8

备注:

,