Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
60 - ZOJ Monthly, June 2007 - 1005
Polymorphism

Time Limit: 5 Seconds      Memory Limit: 32768 KB

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.
With the inheritance relations and the classes which has implemented the specific function input, you program is asked to output in which class the function codes will be runned when an object is asked to execute the function. (As a pure OOP language, multiple inheritance is not considered)

Input

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.

Output

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.

Sample Input

Shape 3
Triangle Shape
Rectangle Shape
Square Rectangle
2
Triangle
Rectangle
3
Triangle
Rectangle
Square

Sample Output

Function 1
Triangle
Rectangle
Rectangle

Author: XIAO, Dong


Submit    Status