가계도

인류학 교수가 고립된 섬에 사는 사람들과 그들의 역사에 관심을 가졌다. 그는 인류학 실험을 하기 위해 그들의 가계도를 수집했다. 실험을 위해 그는 가계도를 컴퓨터로 처리해야 했다. 이를 위해 가계도를 텍스트 파일로 옮겼다. 다음은 가계도를 나타내는 텍스트 파일의 예이다.

John
 Robert
  Frank
  Andrew
 Nancy
  David

각 줄에는 사람의 이름이 들어 있다. 첫 줄의 이름은 이 가계도에서 가장 오래된 조상이다. 가계도에는 가장 오래된 조상의 자손만 들어 있다. 그들의 남편과 아내는 가계도에 나오지 않는다. 어떤 사람의 자녀는 부모보다 한 칸 더 들여쓰기되어 있다. 예를 들어 Robert와 Nancy는 John의 자녀고, Frank와 Andrew는 Robert의 자녀다. David는 Robert보다 한 칸 더 들여쓰기되어 있지만 Robert의 자녀가 아니라 Nancy의 자녀다. 이렇게 가계도를 나타내기 위해 교수는 가계도에서 일부 사람을 제외하여, 어느 누구도 가계도 안에 두 부모가 함께 있지 않게 했다.

실험을 위해 교수는 가족의 문서도 수집하여, 각 가계도에 있는 두 사람의 관계에 대한 문장 집합을 추출했다. 다음은 위 가족에 대한 문장의 예이다.

John is the parent of Robert.
Robert is a sibling of Nancy.
David is a descendant of Robert.

실험을 위해 그는 각 문장이 참인지 거짓인지 확인해야 한다. 예를 들어 위의 처음 두 문장은 참이고 마지막 문장은 거짓이다. 이 작업은 지루하기 때문에 그는 컴퓨터 프로그램으로 확인하려고 한다.

입력은 여러 데이터 세트로 이루어진다. 각 데이터 세트는 가계도 하나와 문장 집합 하나로 구성된다. 각 데이터 세트의 첫 줄에는 두 정수 n (0 < n < 1000)과 m (0 < m < 1000)이 주어지며, 각각 가계도에 있는 이름의 수와 문장의 수를 나타낸다. 입력의 각 줄은 70자 미만이다.

이름은 알파벳 문자로만 이루어진 문자열이다. 가계도에 있는 이름은 20자 미만이다. 가계도의 첫 줄에 있는 이름에는 앞쪽 공백이 없다. 가계도의 나머지 이름은 적어도 하나의 공백으로 들여쓰기되어 있다. 즉, 첫 줄에 있는 사람의 자손이다. 가계도에서 어떤 이름이 k개의 공백으로 들여쓰기되어 있으면, 다음 줄의 이름은 많아야 k + 1개의 공백으로 들여쓰기되어 있다고 가정할 수 있다. 이로써 가장 오래된 조상을 제외한 각 사람은 가계도 안에 부모가 있음이 보장된다. 같은 가계도에 같은 이름이 두 번 나오지 않는다. 가계도의 각 줄 끝에는 불필요한 공백이 없다.

각 문장은 한 줄을 차지하며 다음 형식 중 하나로 쓰인다. 여기서 X와 Y는 가계도에 있는 서로 다른 이름이다.

X is a child of Y.
X is the parent of Y.
X is a sibling of Y.
X is a descendant of Y.
X is an ancestor of Y.

가계도에 나오지 않는 이름은 문장에 쓰이지 않는다. 문장에서 연속한 단어는 하나의 공백으로 구분된다. 각 문장은 줄의 앞과 뒤에 불필요한 공백이 없다.

입력의 끝은 두 개의 0으로 나타낸다.

데이터 세트의 각 문장에 대해 프로그램은 True 또는 False를 한 줄에 출력해야 한다. 출력에서 True 또는 False의 첫 글자는 대문자여야 한다. 각 데이터 세트의 출력 뒤에는 빈 줄이 따라야 한다.