파일 업로드

가계도 조사

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

원지는 몇 세대에 걸쳐 가족 경영 사업을 운영하고 있으며, 그녀의 사업에서 세대를 거슬러 올라가며 일하던 가족들의 기록이 있다.

오래된 기록들을 조사하며, 원지는 현재 회사에 있는 사람들이 서로 어떻게 연결되어 있는지 궁금해졌다. 그녀에게 도움을 주세요!

💻 입력

첫 번째 입력 줄에는 NN (1N1001 \leq N \leq 100)과 두 사람의 이름이 옵니다. 사람의 이름은 각각 최대 10개의 대문자 (AZA \ldots Z)로 이루어진 문자열입니다. 원지 이 입력 줄에서 두 사람 사이의 관계에 궁금해합니다.

다음 NN 줄 각각에는 두 사람의 이름 XXYY가 있습니다. 이는 XXYY의 어머니임을 나타냅니다.

🖨️ 출력

첫 번째 입력 줄에 명시된 두 사람 사이의 관계를 나타내는 한 줄을 출력해야 합니다(간소화를 위해 아래의 예시에서 이 두 사람을 BESSIE와 ELSIE라고 부르겠습니다). 가능한 관계 타입은 아래와 같습니다:

  • BESSIE와 ELSIE가 같은 어머니를 가지고 있다면 'SIBLINGS'을 출력해야 합니다.
  • BESSIE가 ELSIE의 직계 후손일 수 있습니다. 즉, ELSIE가 BESSIE의 어머니, 할머니, 증조할머니, 고조할머니 등일 경우입니다. 이 경우, 'ELSIE is the (relation) of BESSIE'를 출력해야 합니다. 여기서 (relation)은 적절한 관계를 나타내며, 예를 들어 'great-great-grand-mother'가 될 수 있습니다.
  • ELSIE가 BESSIE의 조상의 자식이고(그리고 ELSIE가 BESSIE의 조상이나 여동생이 아닌 경우), 그런 다음 ELSIE는 BESSIE의 이모입니다. 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'를 출력해야 합니다.

다음의 다이어그램은 위의 관계를 도식화하고 있으며, 고려해야 하는 유일한 관계 유형입니다. BESSIE가 ELSIE의 조카인 경우('niece', 즉 여동생의 딸) 등 일부 관계는 필요하지 않음에 주목하십시오.


💻 예제 입력 1
7 AA BB
MOTHER AA
GGMOTHER BB
MOTHER SISTER
GMOTHER MOTHER
GMOTHER AUNT
AUNT COUSIN
GGMOTHER GMOTHER
🖨️ 예제 출력 1
BB is the great-aunt of AA

출처: USACO 2018 US Open Contest, Bronze Problem 3. Family Tree