RiseOJ – 가계도

설명

농부 존은 여러 세대에 걸쳐 물려 내려온 가족 농장을 운영하고 있으며, 그의 소 떼 역시 같은 농장에서 여러 세대를 거슬러 올라가는 혈통을 가지고 있다. 오래된 기록을 살펴보던 농부 존은 현재 소 떼의 소들이 서로 어떤 관계인지 궁금해졌다. 이 일을 도와주자!

출제자: Brian Dean

제약

출제자: Brian Dean

입력 형식

입력의 첫째 줄에 $$N$$ ( $1 \leq N \leq 100$ )과 두 소의 이름이 주어진다. 소 이름은 각각 최대 10개의 대문자( $A \ldots Z$ )로 이루어진 문자열이다. 농부 존은 이 줄에 주어진 두 소 사이의 관계가 궁금하다.

다음 $$N$$ 개의 줄에는 각각 두 소의 이름 $$X$$ 와 $$Y$$ 가 주어지며, 이는 $$X$$ 가 $$Y$$ 의 어미임을 뜻한다.

출력 형식

입력의 첫째 줄에 주어진 두 소 사이의 관계를 나타내는 한 줄을 출력해야 한다(간단히 하기 위해, 아래 예시에서는 이 두 소를 BESSIE와 ELSIE라고 부르자). 가능한 관계의 종류는 다음과 같다.

BESSIE와 ELSIE의 어미가 같으면 "SIBLINGS"를 출력해야 한다.
BESSIE가 ELSIE의 직계 후손일 수 있다. 즉, ELSIE가 BESSIE의 어미(mother), 할머니(grand-mother), 증조할머니(great-grand-mother), 고조할머니(great-great-grand-mother) 등인 경우이다. 이 경우 "ELSIE is the (relation) of BESSIE"를 출력해야 하며, (relation)에는 적절한 관계, 예를 들어 "great-great-grand-mother"가 들어간다.
ELSIE가 BESSIE의 조상의 자식이고 (ELSIE 자신은 BESSIE의 조상도 자매도 아니라면), ELSIE는 BESSIE의 이모(aunt)이다. ELSIE가 BESSIE의 할머니의 자식이면 "ELSIE is the aunt of BESSIE"를, ELSIE가 BESSIE의 증조할머니의 자식이면 "ELSIE is the great-aunt of BESSIE"를, ELSIE가 BESSIE의 고조할머니의 자식이면 "ELSIE is the great-great-aunt of BESSIE"를 출력하는 식이다.
BESSIE와 ELSIE가 그 밖의 다른 방식으로 관계되어 있다면(즉, 공통 조상을 가진다면), 둘은 사촌이며 단순히 "COUSINS"를 출력해야 한다.
BESSIE와 ELSIE에게 공통 조상이 없고 어느 쪽도 다른 쪽의 직계 후손이 아니면 "NOT RELATED"를 출력해야 한다.

다음 그림은 위의 관계들을 이해하는 데 도움이 되며, 고려해야 하는 관계 종류는 이것들뿐이다. "niece"(자매의 딸)와 같은 일부 관계는 필요하지 않다는 점에 주목하라. BESSIE가 ELSIE의 niece라면 ELSIE는 BESSIE의 aunt이기 때문이다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 family.in · 출력을 쓸 파일 family.out

예제 1

입력

7 AA BB
MOTHER AA
GGMOTHER BB
MOTHER SISTER
GMOTHER MOTHER
GMOTHER AUNT
AUNT COUSIN
GGMOTHER GMOTHER

출력

BB is the great-aunt of AA

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > US Open > Bronze

올림피아드 > USACO > 2017-2018 > US Open > Bronze

태그

JudgeUSACO

가계도

평가 및 의견

풀이 제출