CF237D.T-decomposition

You've got a undirected tree s, consisting of n nodes. Your task is to build an optimal T-decomposition for it. Let's define a T-decomposition as follows.

Let's denote the set of all nodes s as v. Let's consider an undirected tree t, whose nodes are some non-empty subsets of v, we'll call them x__i . The tree t is a T-decomposition of s, if the following conditions holds:

1. the union of all x__i equals v;
2. for any edge (a, b) of tree s exists the tree node t, containing both a and b;
3. if the nodes of the tree t x__i and x__j contain the node a of the tree s, then all nodes of the tree t, lying on the path from x__i to x__j also contain node a. So this condition is equivalent to the following: all nodes of the tree t, that contain node a of the tree s, form a connected subtree of tree t.

There are obviously many distinct trees t, that are T-decompositions of the tree s. For example, a T-decomposition is a tree that consists of a single node, equal to set v.

Let's define the cardinality of node x__i as the number of nodes in tree s, containing in the node. Let's choose the node with the maximum cardinality in t. Let's assume that its cardinality equals w. Then the weight of T-decomposition t is value w. The optimal T-decomposition is the one with the minimum weight.

Your task is to find the optimal T-decomposition of the given tree s that has the minimum number of nodes.

你有一棵包含 $ n $ 个节点的无向树 $ s $。你的任务是为其构造一个最优的树分解（T-decomposition）。我们如下定义树分解（T-decomposition）：

记树 $ s $ 的所有节点构成的集合为 $ v $。考虑一棵无向树 $ t $，其每个节点均为 $ v $ 的某个非空子集，我们将其记作 $ x_i $ 。若树 $ t $ 满足以下条件，则称其为树 $ s $ 的一个树分解（T-decomposition）：

1. 所有 $ x_i $ 的并集等于 $ v $；
2. 对于树 $ s $ 中任意一条边 $ (a,,b) $，均存在树 $ t $ 中的一个节点，该节点同时包含 $ a $ 和 $ b $；
3. 若树 $ t $ 中的两个节点 $ x_i $ 和 $ x_j $ 均包含树 $ s $ 中的某节点 $ a $，则树 $ t $ 中连接 $ x_i $ 与 $ x_j $ 的路径上的所有节点也都包含 $ a $。换言之，所有包含树 $ s $ 中节点 $ a $ 的树 $ t $ 的节点，在 $ t $ 中构成一棵连通子树。

显然，满足上述定义的树 $ t $（即树 $ s $ 的树分解）有很多种。例如，仅含一个节点的树 $ t $，其唯一节点为集合 $ v $，便是一个合法的树分解。

我们将节点 $ x_i $ 的基数（cardinality）定义为其中所含的树 $ s $ 的节点个数。在树 $ t $ 中选取基数最大的节点，设其基数为 $ w $。则树分解 $ t $ 的权重（weight）定义为该值 $ w $。所谓最优树分解，即权重最小的树分解。

你的任务是：对给定的树 $ s $，找出一个权重最小的最优树分解，并在所有此类最优树分解中，进一步选择节点数最少的一个。

The first line contains a single integer n (2 ≤ n ≤ 105), that denotes the number of nodes in tree s.

Each of the following n - 1 lines contains two space-separated integers a__i, b__i (1 ≤ a__i, b__i ≤ n; a__i ≠ b__i), denoting that the nodes of tree s with indices a__i and b__i are connected by an edge.

Consider the nodes of tree s indexed from 1 to n. It is guaranteed that s is a tree.

第一行包含一个整数 $n$（$2 \leq n \leq 10^5$），表示树 $s$ 中的节点数量。

接下来的 $n-1$ 行，每行包含两个以空格分隔的整数 $a_i$、$b_i$（$1 \leq a_i, b_i \leq n$；$a_i \neq b_i$），表示树 $s$ 中索引为 $a_i$ 和 $b_i$ 的节点之间存在一条边。

考虑树 $s$ 中从 $1$ 到 $n$ 编号的节点。保证 $s$ 是一棵树。

In the first line print a single integer m that denotes the number of nodes in the required T-decomposition.

Then print m lines, containing descriptions of the T-decomposition nodes. In the i-th (1 ≤ i ≤ m) of them print the description of node x__i of the T-decomposition. The description of each node x__i should start from an integer k__i, that represents the number of nodes of the initial tree s, that are contained in the node x__i. Then you should print k__i distinct space-separated integers — the numbers of nodes from s, contained in x__i, in arbitrary order.

Then print m - 1 lines, each consisting two integers p__i, q__i (1 ≤ p__i, q__i ≤ m; p__i ≠ q__i). The pair of integers p__i, q__i means there is an edge between nodes x__p__i and x__q__i of T-decomposition.

The printed T-decomposition should be the optimal T-decomposition for the given tree s and have the minimum possible number of nodes among all optimal T-decompositions. If there are multiple optimal T-decompositions with the minimum number of nodes, print any of them.

第一行输出一个整数 $m$，表示所求的树分解（T-decomposition）中节点的数量。

接下来输出 $m$ 行，每行描述树分解中的一个节点。第 $i$ 行（$1 \le i \le m$）描述树分解中的节点 $x_i$。每个节点 $x_i$ 的描述以一个整数 $k_i$ 开头，表示初始树 $s$ 中属于节点 $x_i$ 的节点个数；随后在同一行输出 $k_i$ 个互不相同的、以空格分隔的整数——即属于 $x_i$ 的 $s$ 中的节点编号（顺序任意）。

然后输出 $m-1$ 行，每行包含两个整数 $p_i,\, q_i$（满足 $1 \le p_i,\, q_i \le m$ 且 $p_i \ne q_i$），表示树分解中节点 $x_{p_i}$ 与 $x_{q_i}$ 之间存在一条边。

所输出的树分解应为给定树 $s$ 的最优树分解，且在所有最优树分解中，其节点数 $m$ 应达到最小。若存在多个节点数最少的最优树分解，输出其中任意一个即可。