Ghost

A ghost is haunting South Korea. The ghost of KOI 2022 Round 2...

The KOI city has $N$ intersections and $N - 1$ bidirectional roads, and any two distinct intersections can reach each other using only roads. In other words, the road network is a tree. The roads lie on a two-dimensional plane, and no two roads cross except at their endpoints.

Until a few decades ago, KOI city was a small town. As people moved in, it grew quickly. During this rapid expansion, the mayor numbered the intersections from $1$ to $N$ for administrative convenience. The numbering has the following properties.

• Intersection $1$ is the city center, and it is adjacent to at least $2$ roads.
• The numbers form one of the preorder traversals of the tree rooted at intersection $1$.
• For every intersection, look at the adjacent intersections (directly connected by a road) and pick the one with the smallest number. Starting from that intersection, list the numbers of the adjacent intersections in counterclockwise order. The numbers increase.

As more people arrived, traffic congestion got worse. To deal with it, the mayor connected the intersections with the weakest transport links, meaning those adjacent to exactly one road, with an outer ring road. Let $\{v_1, v_2, \dots, v_k\}$ be the numbers of the intersections adjacent to exactly one road, sorted in increasing order. For every $1 \le i \le k$, the mayor built a bidirectional road between intersection $v_i$ and intersection $v_{(i \bmod k)+1}$. Because of the numbering, the ring roads can be added so that no two roads cross except at their endpoints.

Workers do not want to turn a tree into a graph. Congestion relief shortens commutes, and capitalists then find it easier to exploit workers. Workers want to return to the good old days when HLD and centroid decomposition could be done on the KOI city tree. First, they plan to overthrow the capitalists in a socialist revolution. Then they want to build a new tree as follows, to rebuild the structure of the original KOI city.

• The new tree has at most $4N$ vertices. If the new tree has $K$ vertices, number them $1, 2, \ldots, K$.
• Vertex $i$ of the new tree has a set $X_i$, which is a subset of $\{1, \ldots, N\}$.
• For every road $(u, v)$ of the original KOI city, there is some set $X_i$ that contains both $u$ and $v$. Roads here include the original tree roads and the outer ring roads.
• For every $1 \le j \le N$, let $S_j$ be the set of new tree vertices $i$ with $j \in X_i$. Each $S_j$ must be nonempty and revolutionary.
• For every $i$, $|X_i| \le 4$ must hold. (Solutions with $|X_i| \le 5$ may receive partial credit.)

A vertex subset $S$ of the new tree is revolutionary if the following holds. For any two distinct vertices $u$ and $v$ in $S$, if $u$ and $v$ can be connected by walking through the new tree using only vertices of $S$, then we say $u$ and $v$ are "connected within $S$". $S$ is revolutionary when every pair of distinct vertices $u, v$ in $S$ is always connected within $S$.

For example, consider the following new tree.

If $S = \{1, 2, 3, 4, 5, 6\}$, then $(1, 2)$, $(3, 5)$, and $(4, 6)$ are each connected within $S$. However, $(1, 6)$ and $(2, 6)$ are not connected within $S$.

Given the road network of KOI city, output the new tree and the set $X_i$ of each vertex.

The first line contains $N$, the number of intersections in KOI city.

The next $N - 1$ lines follow. The $i$-th of these lines contains one integer $p_i$, which means there is a bidirectional road between intersection $p_i$ and intersection $i + 1$.

The roads given in the input are not the outer ring roads.

On the first line, print $K$, the number of vertices in the new tree. It must satisfy $1 \le K \le 4N$.

Next, print $K$ lines. The first integer on the $i$-th line is the size of $X_i$, followed by the $|X_i|$ distinct integers of $X_i$, separated by spaces.

Then print $K - 1$ lines describing the edges of the new tree, in order.

A valid answer always exists.

• $4 \le N \le 100\,000$
• $1 \le p_i \le i$

$X_i$ may be the empty set.

If there were no size limit on $X_i$, a trivial answer would exist: $K = 1$ and $X_1 = \{1, 2, \ldots, N\}$.