60 - ZOJ Monthly, June 2007 - 1005
One of your old friends is now developping a new programming language. He want 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 want 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 (function), the first line is the name of the base class which has declared the function as an abstract function (or totally virtual function in C++) and an integer N (1 <= N <= 30,000), which is the number of classes which are derived from the base class directly or indirectly, 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. After that there is an integer M (0 <= M <= N + 1), the number of classes which have implemented this function. Then M lines follow, each contains one class name C, you may assume that C is either one of the A's or the base class. Finally an integer L (1 <= L <= 30,000) and L lines with each line one class name D, of which an instance is now being asked to executed the function. 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 "Function K" where K is the case index start from 1.
For each D, you program should print the name of the class in which the function codes will be executed (D or the nearest base class of D which has implemented the function). If there is not such a class (so the input is an instance of an abstarct class which cannot exist), output "Exception".
Print a blank line between every two cases.
Shape 3 Triangle Shape Rectangle Shape Square Rectangle 2 Triangle Rectangle 3 Triangle Rectangle Square
Function 1 Triangle Rectangle Rectangle
Author: XIAO, Dong