CodeForces - 237D T-decomposition 构造

D. T-decomposition

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 xi 

. The tree t is a T-decomposition of s, if the following conditions holds:

1. the union of all xi 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 xi and xj contain the node a of the tree s, then all nodes of the tree t, lying on the path from xi to xj 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 xi 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.

Input

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 ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi), denoting that the nodes of tree s with indices ai and bi are connected by an edge.

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

Output

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 xi of the T-decomposition. The description of each node xi should start from an integer ki, that represents the number of nodes of the initial tree s, that are contained in the node xi. Then you should print ki distinct space-separated integers — the numbers of nodes from s, contained in xi, in arbitrary order.

Then print m - 1 lines, each consisting two integers pi, qi (1 ≤ pi, qi ≤ m; pi ≠ qi). The pair of integers pi, qi means there is an edge between nodes xpi and xqi 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.

Examples

input

Copy

2
1 2

output

Copy

1
2 1 2

input

Copy

3
1 2
2 3

output

Copy

2
2 1 2
2 2 3
1 2

input

Copy

4
2 1
3 1
4 1

output

Copy

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

题意：

现在给你的是一个S树，然后让你构造一个满足以下几个条件的树T

• 树T中的点为树S ‘点’ 的集合，也就是数T中的点实际上是由多个S中的点组成的，并且树T上的点的集合的并集是S树点的全集
• 如果S上有边（a,b）那么T树上必须有某个结点，包含a和b这两个点
• 如果几个T上的点，包含着相同的S上的点，那么这几个T上的点要彼此相连

最后树T有一个基数，也就是数T上的点包含的最多树S点的个数，让你找出最小的树T的基数

分析：

 

其实S树的每一条边看成T树的一个点，这样T树的基数为2，这样就满足了条件一和二，对于第三个条件，我们对S数相邻的两条边连

起来当作T树的边即可。

 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long long ll ;
const int N=200000+7;
int a[N],b[N];
vector<int>edge[N];
int main()
{
   // freopen("input.txt","r",stdin);
   // freopen("output.txt","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
   {
      scanf("%d%d",&a[i],&b[i]);
      edge[a[i]].push_back(i);
      edge[b[i]].push_back(i);
   }
   printf("%d\n",n-1);
   
   for(int i=1;i<n;i++)
   {
      printf("2 %d %d\n",a[i],b[i]);
   }
   for(int i=1;i<=n;i++)
   {
      for(int j=0;j<edge[i].size()-1;j++)
      {
        printf("%d %d\n",edge[i][j],edge[i][j+1]);
      }
   }
   return 0 ;
}