유령

하나의 유령이 대한민국을 배회하고 있다. KOI 2022 2차 대회라는 유령이...

KOI 도시는 $N$개의 교차로와 $N - 1$개의 양방향 도로로 이루어져 있으며, 임의의 서로 다른 두 교차로를 도로만 사용해서 오갈 수 있다. 즉, 도시의 도로망은 트리 구조다. 도로는 2차원 평면 위에 있으며, 두 도로는 끝점을 제외한 위치에서 교차하지 않는다.

몇십 년 전까지만 해도 KOI 도시는 작은 마을이었다. 사람이 유입되고 규모가 커지면서 도시는 급격히 팽창했다. 이 과정에서 시장은 행정 편의를 위해 교차로에 $1$ 이상 $N$ 이하의 번호를 매겼다. 이 번호 체계는 다음 성질을 만족한다.

• $1$번 교차로는 도시의 중심이며, $2$개 이상의 도로와 인접함이 보장된다.
• 교차로에 매겨진 번호는 $1$번 교차로를 루트로 한 트리의 전위 순회 순서 (Preorder) 중 하나다.
• 모든 교차로에 대해, 인접한 (도로로 직접 연결된) 교차로 중 번호가 가장 작은 교차로를 생각하자. 이 교차로를 기준으로 시계 반대 방향으로 인접한 교차로의 번호를 나열하면, 번호는 증가한다.

KOI 도시에 사람이 많이 유입되면서 교통 체증이 심해졌다. 시장은 이를 해결하기 위해 교통 인프라가 가장 빈약한 도시들, 즉 도로 1개와만 인접한 교차로들을 외곽 순환 도로로 이었다. 도로 1개와만 인접한 교차로들의 번호를 증가하는 순서대로 나열한 리스트를 $\{v_1, v_2, \dots, v_k\}$라 하자. 시장은 모든 $1 \le i \le k$에 대해 $v_i$번 교차로와 $v_{(i \bmod k)+1}$번 교차로를 잇는 양방향 도로를 건설했다. 번호 체계의 특성상, 외곽 순환 도로는 두 도로가 끝점을 제외한 위치에서 교차하지 않도록 이을 수 있다.

하지만 노동자들은 교통 체증이 해소되어 출퇴근 시간이 줄어들면 자본가들이 노동자를 착취하기 쉬워질 뿐이라고 본다. 그래서 트리를 그래프로 만드는 일을 반기지 않는다. 노동자들은 자본가들의 역겨운 수작에 넘어가지 않고, KOI 도시 트리에서 HLD와 센트로이드 분할을 할 수 있었던 좋은 옛날로 돌아가고 싶어 한다. 노동자들은 먼저 사회주의 혁명을 일으켜 자본가들을 몰아내고, 다음 조건을 만족하는 새로운 트리를 만들어 기존 KOI 도시의 구조를 재건하려 한다.

• 새로운 트리의 정점은 $4N$개 이하다. 새로운 트리의 정점이 $K$개일 때, 각 정점의 번호를 $1, 2, \ldots, K$로 나타낸다.
• 새로운 트리의 $i$번째 정점에는 집합 $X_i$가 있으며, $X_i$는 $\{1, \ldots, N\}$의 부분집합이다.
• 원래 KOI 도시의 모든 도로 $(u, v)$에 대해, $u$와 $v$를 모두 포함하는 집합 $X_i$가 존재한다. 여기서 모든 도로에는 원래 트리를 이루는 도로와 외곽 순환 도로가 모두 포함된다.
• 모든 $1 \le j \le N$에 대해, $j \in X_i$를 만족하는 정점들의 집합을 $S_j$라 하자. $S_j$는 공집합이 아니어야 하며, 혁명적 집합이어야 한다.
• 모든 $i$에 대해 $|X_i| \le 4$를 만족해야 한다. ($|X_i| \le 5$를 만족하면 부분 점수를 받을 수 있다.)

새로운 트리의 정점 부분집합 $S$가 혁명적이라는 것은 다음과 같다. $S$에 속하는 서로 다른 두 정점 $u$, $v$에 대해, $S$에 속한 정점만 이용해서 새로운 트리 위에서 $u$에서 $v$로 오갈 수 있다면, "$u$와 $v$는 $S$ 위에서 연결되어 있다"고 한다. $S$가 혁명적이라는 것은, $S$에서 서로 다른 두 정점 $u$, $v$를 골랐을 때 $u$와 $v$가 항상 $S$ 위에서 연결되어 있음을 뜻한다.

예를 들어, 아래와 같은 새로운 트리를 생각하자.

$S = \{1, 2, 3, 4, 5, 6\}$이라면, $(1, 2)$, $(3, 5)$, $(4, 6)$은 각각 $S$ 위에서 연결되어 있다. 그러나 $(1, 6)$과 $(2, 6)$은 각각 $S$ 위에서 연결되어 있지 않다.

노동자들을 도와, KOI 도시의 도로망이 주어졌을 때 새로운 트리와 각 정점의 집합 $X_i$를 출력하라.

첫 번째 줄에 KOI 도시의 교차로 수 $N$이 주어진다.

이후 $N - 1$개의 줄이 주어진다. 이 중 $i$번째 줄에는 정수 $p_i$ 하나가 주어진다. 이는 교차로 $p_i$와 교차로 $i + 1$을 잇는 양방향 도로가 존재한다는 뜻이다.

입력으로 주어지는 도로들은 외곽 순환 도로가 아니다.

첫 번째 줄에 새로운 트리의 정점 수 $K$를 출력하라. $1 \le K \le 4N$을 만족해야 한다.

이후 $K$개의 줄을 출력하라. $i$번째 줄의 첫 번째 정수는 집합 $X_i$의 크기다. 이어서 $X_i$에 속하는 서로 다른 정수들을 공백으로 구분하여 출력한다.

이후 $K - 1$개의 줄에 걸쳐 새로운 트리의 간선을 차례대로 출력하라.

정답이 항상 존재함을 증명할 수 있다.

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

$X_i$는 공집합이어도 된다.

만약 $X_i$의 크기 조건이 없다면, $K = 1$, $X_1 = \{1, 2, \ldots, N\}$으로 잡는 자명한 해가 존재한다.