Is-A? Has-A? Who Knowz-A?
시간 제한2초메모리 제한512 MB
클래스 사이의 상속 관계와 필드 관계가 주어지면 한 클래스가 다른 클래스를 상속하거나 필드로 갖는지 질의마다 판정합니다.
문제
객체 지향 프로그래밍에는 is-a와 has-a라는 두 가지 익숙한 관계가 있다. 두 클래스 A와 B에 대해, A가 B의 서브클래스이면 A is-a B라고 하고, A의 필드 중 하나의 타입이 B이면 A has-a B라고 한다. 예를 들어 ICPC++라는 객체 지향 언어가 있어 Figure E.1과 같은 코드가 있다고 하자. 여기서 클래스 Day는 Time is-a이고, 클래스 Appointment는 DateBook이자 Reminder이며, 클래스 Appointment는 Day has-a이다.
class Day extends Time class Appointment extends Datebook, Reminder
{ {
... private Day date;
} ...
}
Figure E.1: Two ICPC++ classes.
이 두 관계는 추이적이다. 예를 들어 A is-a B이고 B is-a C이면 A is-a C임을 알 수 있다. 이는 앞 문장의 모든 is-a를 has-a로 바꾸어도 성립한다. is-a와 has-a의 조합에서도 성립한다. 위의 예에서 Appointment는 Day has-a이고 Day는 Time is-a이므로 Appointment는 Time has-a이다. 마찬가지로 클래스 DateBook이 Year has-a이면 Appointment는 DateBook is-a이므로 Appointment는 Year has-a이다.
이 문제에서는 is-a와 has-a 관계의 집합과 A is/has-a B 형태의 질의 집합이 주어진다. 각 질의가 참인지 거짓인지 판별해야 한다.
입력
입력은 두 정수 n과 m (1 ≤ n, m ≤ 10, 000)으로 시작한다. n은 주어지는 is-a와 has-a 관계의 수이고 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”는 제외).
출력
각 질의에 대해 질의 번호(1부터 시작)와 질의가 참인지 거짓인지를 출력한다.