아빠

시간 제한1초메모리 제한128 MB

요약
일관된 가족 관계가 주어질 때 배우자, 부모, 자녀, 성별을 추론하고 조카나 할아버지 같은 친족 질문에 yes, no, unknown으로 답한다.
난이도

어려움10점 중 8점

유형
그래프, 유니온 파인드, 시뮬레이션, 구현
정답자
아직 제출이 없습니다

문제

부모님 댁 다락방을 정리하다가, 당신의 조상들 사이의 관계를 적어 놓은 문서가 가득 든 상자를 발견했습니다. 이 문서들을 바탕으로, 문서가 함의하는 여러 관계에 대한 질문에 답하려고 합니다. 다행히 모든 조상의 이름이 서로 다르므로, 혼동 없이 많은 사실을 추론할 수 있습니다.

주어졌거나 추론된 모든 관계는 다음 규칙을 만족합니다.

  • 각 사람은 남성, 여성, 또는 성별을 알 수 없음(자료로 결정되지 않음) 중 하나이다.
  • 각 사람은 이성인 배우자를 최대 한 명 가질 수 있으며, X가 Y의 아내인 것과 Y가 X의 남편인 것은 서로 동치이다.
  • 각 사람은 자료로부터 추론되는 어머니를 최대 한 명, 아버지를 최대 한 명 가질 수 있다.
  • 어떤 사람이 어머니와 아버지를 모두 가진다면, 그 어머니와 아버지는 부부이다.
  • 어떤 사람의 배우자의 자녀는 그 사람의 자녀이기도 하다.
  • 아들(또는 딸)의 배우자는 딸(또는 아들)로 간주하지 않는다. 즉 '아들'과 '딸'은 항상 친자녀를 뜻한다.

주어지는 정보는 항상 모순이 없으며, 위 규칙으로 명시되거나 함의되는 것 외의 숨은 관계는 없다고 가정해도 됩니다.

입력

입력의 첫 부분은 알려진 관계의 목록으로, 한 줄에 하나씩 다음 형식으로 주어집니다.

NAME is NAME's RELATIONSHIP.

여기서 NAME은 소문자 알파벳으로 이루어진 단어이며(절대 is가 아님), RELATIONSHIP은 다음 중 하나입니다.

  • wife (아내)
  • husband (남편)
  • daughter (딸)
  • son (아들)
  • mother (어머니)
  • father (아버지)

이 부분은 빈 줄로 끝납니다. 알려진 관계는 적어도 하나 주어지며, 알려진 관계에 등장하는 서로 다른 이름은 최대 100개입니다.

그 다음에는 질문 목록이 한 줄에 하나씩 다음 형식으로 이어집니다.

is NAME NAME's RELATIONSHIP?

NAME은 위와 같고, RELATIONSHIP은 다음 중 하나입니다.

  • wife (아내)
  • husband (남편)
  • daughter (딸)
  • son (아들)
  • mother (어머니)
  • father (아버지)
  • niece (조카딸): 어떤 W와 Z가 존재하여 X가 W의 딸이고, W와 Y가 Z의 서로 다른 두 자녀이면 X는 Y의 조카딸이다.
  • nephew (조카): 어떤 W와 Z가 존재하여 X가 W의 아들이고, W와 Y가 Z의 서로 다른 두 자녀이면 X는 Y의 조카이다.
  • grandfather (할아버지): 어떤 Z가 존재하여 X가 Z의 아버지이고, Z가 Y의 아버지 또는 어머니이면 X는 Y의 할아버지이다.
  • grandmother (할머니): 어떤 Z가 존재하여 X가 Z의 어머니이고, Z가 Y의 아버지 또는 어머니이면 X는 Y의 할머니이다.
  • grandson (손자): 어떤 Z가 존재하여 X가 Z의 아들이고, Z가 Y의 자녀이면 X는 Y의 손자이다.
  • granddaughter (손녀): 어떤 Z가 존재하여 X가 Z의 딸이고, Z가 Y의 자녀이면 X는 Y의 손녀이다.

질문에 등장하는 모든 이름은 알려진 관계에도 등장합니다. 질문 목록은 파일의 끝에서 종료됩니다.

출력

각 질문에 대해, 답을 결정할 수 있으면 yes 또는 no를, 관련된 사람의 성별을 알려진 관계로부터 결정할 수 없어 답이 yes일 수도 no일 수도 있으면 unknown을 한 줄에 출력합니다.

예제1

  1. 예제 1

    입력
    john is mary's husband.
    john is tom's father.
    mary is jane's mother.
    jane is anna's mother.
    
    is mary john's wife?
    is jane mary's daughter?
    is tom mary's husband?
    is anna jane's daughter?
    
    예상 출력
    yes
    yes
    no
    unknown