길들여지지 않은 나무

루트가 있는 이진 트리 $T$가 주어진다. $T$의 모든 내부 정점은 정확히 두 개의 자식(왼쪽 자식과 오른쪽 자식)을 가지며, 모든 잎에는 라벨이 붙어 있다. 라벨은 영어 소문자로 이루어진 비어 있지 않은 문자열이고, 서로 다른 잎이 같은 라벨을 가질 수도 있다.

라벨 $\ell$에 대해 트리 $T(\ell)$을 다음과 같이 정의한다.

• $T(\ell)$의 잎은 라벨이 $\ell$인 $T$의 잎들이다.
• 또한 왼쪽 서브트리와 오른쪽 서브트리가 모두 라벨이 $\ell$인 잎을 하나 이상 포함하는 $T$의 내부 정점을 모두 $T(\ell)$에 포함시킨다.
• $T(\ell)$에 포함된 두 정점 $u$와 $v$는, $T$에서 둘을 잇는 경로가 $T(\ell)$에 포함된 다른 정점을 지나지 않을 때 간선으로 연결된다.

$T$에 등장하는 모든 라벨에 대해 트리 $T(\ell)$을 구하는 프로그램을 작성하라.

표준 입력의 각 줄은 $T$의 정점 하나를 설명한다. 트리는 전위 순회(pre-order) 순서로 주어진다. 각 (부분)트리의 첫 줄에는 루트가 오고, 그 루트가 내부 정점이면 이어서 왼쪽 서브트리의 설명이, 그다음 오른쪽 서브트리의 설명이 온다. 별표 * 하나만 있는 줄은 내부 정점을 뜻한다. 소문자 문자열이 있는 줄은 잎을 뜻하며 그 잎의 라벨을 나타낸다. 라벨은 비어 있지 않고 a부터 z까지의 소문자로만 이루어진다. 모든 라벨의 길이 합은 $1\,000\,000$을 넘지 않는다(라벨은 그것이 등장하는 잎마다 한 번씩 센다).

정점은 입력에 등장하는 순서대로 $1$번부터 번호를 매긴다. 즉, 정점의 번호는 그 정점이 적힌 줄 번호와 같다.

모든 트리 $T(\ell)$의 설명을 라벨 $\ell$의 사전순으로 한 줄에 하나씩 출력한다. 각 설명은 입력과 마찬가지로 전위 순회 순서로 쓰되, 트리에 속한 정점들의 번호를 출력한다. 즉, 루트의 번호를 출력하고, 루트가 잎이 아니라면 이어서 왼쪽 서브트리와 오른쪽 서브트리의 설명을 출력한다.