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。