가계도 연구

요즘 많은 사람들이 자신의 조상을 찾는 일에 관심을 가진다. 이런 작업은 보통 여러 회사가 판매하는 가족사(family history) 소프트웨어로 이루어지는데, 이 소프트웨어는 값이 비싸고 McDoze X 운영체제에서만 동작한다. 이를 대신할 오픈 소스 프로그램을 작성하라.

프로그램은 한 줄에 하나씩 주어지는 명령들을 읽는다. 명령의 형식은 다음 문법을 따른다.

command     ::= birth
            ::= death
            ::= ancestors
            ::= descendants
            ::= QUIT

birth       ::= BIRTH child : date : mother : father
death       ::= DEATH person : date
ancestors   ::= ANCESTORS person
descendants ::= DESCENDANTS person

child       ::= name
mother      ::= name
father      ::= name
person      ::= name
date        ::= name

name        ::= any sequence of characters that does not begin or end
                with a space and does not contain a colon

입력의 공백은 이름(name) 안에 포함된 경우를 제외하고 모두 무시된다. BIRTH와 DEATH 명령은 각각 한 사람의 출생과 사망을 기록하며, 모든 사람의 이름은 서로 다르다고 가정해도 된다. ANCESTORS와 DESCENDANTS 명령은 질의로, 앞선 BIRTH·DEATH 명령으로 기록된 정보를 이용해 지정한 사람의 가계도(또는 역방향 가계도)를 출력한다. QUIT 명령은 입력의 끝을 나타낸다.

BIRTH, DEATH, QUIT 명령은 아무것도 출력하지 않는다. 각 ANCESTORS(DESCENDANTS) 명령에 대해 다음을 출력한다.

1. "ANCESTORS of"("DESCENDANTS of") 뒤에 그 사람의 이름을 붙인 줄을 출력한다.
2. 바로 윗줄보다 2칸 들여쓴 뒤, 그 사람의 부모(자식) 중 알파벳순으로 첫 번째를 출력한다. 이름 뒤에 그 부모(자식)의 출생일, 공백 하나, 하이픈을 차례로 붙이고, 그 부모(자식)가 사망했다면 다시 공백 하나와 사망일을 덧붙인다. 그 부모(자식)의 출생 기록이 없으면 이름만 출력한다.
3. 그 부모(자식)에 대한 조상(자손) 정보를 다시 2칸 더 들여써서 같은 방식(2~4단계)으로 출력한다.
4. 나머지 부모(자식)에 대해 2~4단계를 반복하며, 들여쓰기는 앞의 부모(자식)와 동일하게 한다.

연속한 두 명령의 출력 사이에는 빈 줄을 하나 남긴다.

제약:

• 입력의 각 줄은 100자를 넘지 않는다.
• 입력은 최대 250줄이다.
• 모든 DEATH, ANCESTORS, DESCENDANTS 명령은 이미 BIRTH 명령에 등장한 이름을 가리킨다.
• QUIT는 입력의 마지막 줄에만 등장한다.