is-a? has-a? 누가 알까?

객체 지향 프로그래밍에는 is-a 관계와 has-a 관계가 있다. 두 클래스 A와 B에 대해, A가 B의 서브클래스이면 A is-a B라고 한다. A의 필드 중 하나가 B 타입이면 A has-a B라고 한다. 예를 들어 아래 그림과 같은 코드를 쓰는 객체 지향 언어 ICPC++가 있다고 하자. 여기서 Day는 Time의 서브클래스이므로 Day is-a Time이고, Appointment는 Datebook이면서 Reminder이며, Day 타입 필드가 있으므로 Appointment has-a Day이다.

class Day extends Time        class Appointment extends Datebook, Reminder
{                             {
    ...                           private Day date;
}                                 ...
                              }

그림 1: ICPC++ 클래스 두 개.

두 관계는 모두 추이적이다. A is-a B이고 B is-a C이면 A is-a C이다. 앞 문장의 is-a를 모두 has-a로 바꾸어도 성립한다. 두 관계를 섞어도 성립한다. 위 예에서 Appointment has-a Day이고 Day is-a Time이므로 Appointment has-a Time이다. 마찬가지로 Datebook has-a Year라면 Appointment is-a Datebook이므로 Appointment has-a Year이다.

정리하면 관계는 다음 네 규칙으로 유도한다.

• A is-a B이고 B is-a C이면 A is-a C이다.
• A has-a B이고 B has-a C이면 A has-a C이다.
• A is-a B이고 B has-a C이면 A has-a C이다.
• A has-a B이고 B is-a C이면 A has-a C이다.

또 모든 클래스 x에 대해 x is-a x는 참이다.

is-a 관계와 has-a 관계의 목록, 그리고 A is-a B 또는 A has-a B 형태의 질의 목록이 주어진다. 각 질의가 참인지 거짓인지 판정하라.

첫 줄에 정수 $n$과 $m$이 주어진다 ($1 \le n, m \le 10000$). $n$은 주어지는 관계의 개수, $m$은 질의의 개수다.

다음 $n$개 줄에는 관계가 한 줄에 하나씩 c1 r c2 형식으로 주어진다. c1과 c2는 공백이 없는 한 단어짜리 클래스 이름이고 대소문자를 구분한다. r은 문자열 is-a 또는 has-a다. 그 다음 $m$개 줄에는 질의가 같은 형식으로 한 줄에 하나씩 주어진다.

$n + m$개 줄에 나오는 서로 다른 클래스 이름은 최대 $500$개다. 마지막 $m$개 줄에 나오는 클래스 이름은 모두 앞의 $n$개 줄에 적어도 한 번 나온다. 주어진 클래스 사이의 모든 is-a 관계와 has-a 관계는 $n$개의 관계에서 유도된다. is-a 관계는 순환하지 않는다. 다만 x is-a x라는 자명한 관계는 항상 참이다. has-a 관계는 순환할 수 있고, 이때 x has-a x가 참이 되기도 한다.

질의마다 한 줄씩, 질의 번호와 참 거짓을 출력한다. 질의 번호는 1부터 시작한다. $i$번째 질의가 참이면 Query i: true를, 거짓이면 Query i: false를 출력한다. 예를 들어 두 번째 질의가 거짓이면 그 줄은 Query 2: false다.