← 返回题目列表

Codeforces · 638/C

C. 道路改善

中文机器翻译题面 查看原题

Berland 有 n 个城市和 n - 1 条双向道路。每条道路都连接一些城市,从任何城市您都可以仅使用给定的道路到达任何其他城市。

每个城市只有一个修理队。为了修复某条道路,你需要在道路相连的城市中派驻两个团队同时工作一天。两个大队全天都修一条路,当天不能参与修其他路。但那天抢修大队却无能为力。

确定修复所有道路所需的最少天数。这些旅无法改变他们最初所在的城市。

输入

输入的第一行包含一个正整数 n (2 ≤ n ≤ 200 000) — Berland 的城市数量。

接下来的 n - 1 行每行包含两个数字 ui, vi,意味着第 i 条路连接城市 ui 和城市 vi (1 ≤ ui, vi ≤ n, ui ≠ vi)。

输出

第一个打印数字 k — 修复伯兰所有道路所需的最少天数。

在接下来的 k 行中,打印每 k 天应修复的道路的描述。在第 i 行,首先打印数字 di——第 i 天应该修复的道路数量,然后打印 di 空格分隔的整数——第 i 天应该修复的道路数量。道路根据输入中的顺序从 1 开始编号。

如果有多个变体,您可以打印其中任何一个。

示例

输入 #1

4
1 2
3 4
3 2

输出 #1

2
2 2 1
1 3

输入 #2

6
3 4
5 4
3 2
1 3
4 6

输出 #2

3
1 1
2 2 3
2 4 5

注意

在第一个示例中,您可以在两天内修复所有道路,例如,如果您在第一天修复道路 1 和 2,在第二天修复道路 3。