题目描述

给定一棵 $n$ 个结点的无根树 $s$，它的点集为 $V$。你需要构造出一棵无根树 $t$，每个结点 $x_i$ 是 $V$ 中的一个非空子集。这棵树需要满足下列要求：

• 所有 $x_i$ 的并集为 $V$。
• 对于树 $s$ 中的任意一条边 $(a,b)$，在 $t$ 中都能够找到一个集合 $x$ 使得 $a,b\in x$。
• 对于树 $s$ 中的任意一个点 $a$，所有在 $t$ 中包含了 $a$ 的集合构成了一个连通块。

设你构造出来的树 $t$ 的价值为 $t$ 中最大集合的大小。你的构造需要满足在价值最小的前提下，集合个数最少。$1\le n\le 10^5$。

输入格式

第一行，输入 $n$。

接下来 $n-1$ 行，每行输入两个数 $a,b$ 表示树 $s$ 中的一条边。

输出格式

第一行，输出 $t$ 中的集合个数 $k$。

接下来 $k$ 行，每行表示一个集合。第一个数输出集合的大小 $p$，接下来 $p$ 个数输出这个集合中的元素。

接下来 $k-1$ 行，每行输出两个数 $a,b$，表示连接树 $t$ 中的第 $a$ 个和第 $b$ 个集合。