← 返回题目列表

Codeforces · 237/D

D. T 分解

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

你有一个无向树 s,由 n 个节点组成。您的任务是为其构建最佳 T 分解。让我们如下定义 T 分解。

让我们将所有节点 s 的集合表示为 v。让我们考虑一棵无向树 t,其节点是 v 的一些非空子集,我们将它们称为 xi $$( x _ { i } \subseteq v )$$。如果满足以下条件,则树 t 是 s 的 T 分解:

1. 所有 xi 的并集等于 v;
2. 对于树 s 的任意边 (a, b) 都存在树节点 t,其中同时包含 a 和 b;
3. 如果树 t 的节点 xi 和 xj 包含树 s 的节点 a,则位于从 xi 到 xj 的路径上的树 t 的所有节点也包含节点 a。所以这个条件等价于:树t的所有节点,包含树s的节点a,形成树t的连通子树。

显然有许多不同的树 t,它们是树 s 的 T 分解。例如,T 分解是由单个节点组成的树,等于集合 v。

让我们将节点 xi 的基数定义为树 s 中包含该节点的节点数。让我们选择 t 中基数最大的节点。我们假设它的基数等于 w。那么T分解的权重t就是值w。最佳 T 分解是权重最小的分解。

您的任务是找到具有最少节点数的给定树 s 的最佳 T 分解。

输入

第一行包含一个整数 n (2 ≤ n ≤ 105),表示树 s 中的节点数。

以下 n - 1 行中的每一行都包含两个空格分隔的整数 ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi),表示索引为 ai 和 bi 的树 s 的节点通过边连接。

考虑从 1 到 n 索引的树 s 的节点。保证s是一棵树。

输出

在第一行中打印一个整数 m,表示所需 T 分解中的节点数。

然后打印 m 行,包含 T 分解节点的描述。在其中的第 i 个(1 ≤ i ≤ m)中打印 T 分解的节点 xi 的描述。每个节点 xi 的描述应该从整数 ki 开始,它表示节点 xi 中包含的初始树 s 的节点数。然后,您应该以任意顺序打印 ki 个不同的空格分隔整数 - s 中包含在 xi 中的节点数。

然后打印 m - 1 行,每行包含两个整数 pi, qi (1 ≤ pi, qi ≤ m; pi ≠ qi)。整数pi、qi对表示T分解的节点xpi和xqi之间有一条边。

打印的 T 分解应该是给定树的最佳 T 分解,并且在所有最佳 T 分解中具有尽可能少的节点数。如果存在多个节点数最少的最优 T 分解,则打印其中任意一个。

示例

输入 #1

2
1 2

输出 #1

1
2 1 2

输入 #2

3
1 2
2 3

输出 #2

2
2 1 2
2 2 3
1 2

输入 #3

4
2 1
3 1
4 1

输出 #3

3
2 2 1
2 3 1
2 4 1
1 2
2 3