ZOJ Problem Set - 2999
One of your old friends is now developing a new programming language. He wants to make it the best programming language ever, or at least the best at most phases. So it is an Object-Oriented Programming language of course. He thinks most OOP languages at present are too inefficient with the handling of inheritance and polymorphism, and he wants to make this quicker in his own language. However, he isn't good at algorithm himself, so he comes to you, a well-known ACMer, and is now asking you to help him.
For each test case (project), the first line is the name of the common base class in the language (the base class of all classes in this language, because the language is still in developing, its name has not been fixed) and an integer N (1 <= N <= 30,000), the number of classes in this project, then N lines follow. Each line contains two class names A and B, specifying that class A is derived from class B. All A's will be different in the N lines, and you may assume that all classes will be derived from the common base class directly or indirectly. After that there is an integer M (1 <= M <= 30,000), the number of pairs of classes to be checked and then M lines follow. Each line contains two class names C and D, you are asked to check whether an instance of class C is class D (an instance of class D or a class derived from D, for example, if you're a student, you're a human, because student is a derived class of human). All class name will be non-space charaters with length no more than 255.
These's a blank line between every two cases, processing to the end of file.
For each test case, in the first line output "Project K" where K is the case index starts from 1.
For each pairs of C and D, you program should print "Yes" or "No" in one line according to whether an instance of class C is class D.
Print a blank line between consecutive cases.
Object 3 Integer Object List Object LinkedList List 3 Integer Object LinkedList List Integer List
Project 1 Yes Yes No
Author: XIAO, Dong
Source: ZOJ Monthly, June 2008