We are observing class declarations in an object-oriented programming language similar to C++. Each class declaration is of the form K : P1 P2 ... Pk ;
where shape : ;
is a declaration of class shape
that does not inherit any other class, whereas square : shape rectangle ;
is a declaration of class square
that inherits classes shape
and rectangle
.
If class
- Classes
and are derived from . - Class
is derived from both and . - Neither is class
derived from , nor is class derived from .
You are given a series of class declarations to be processed sequentially, and determine for each one whether it is correctly declared. The correctly declared classes are added to the hierarchy, while the incorrect ones are discarded. Declaration K : P1 P2 ... Pk ;
is correctly declared if the following holds:
- Class
hasn't been declared yet. - All classes
have been previously declared. Notice that this condition ensures that a class can never be derived from itself, or that cycles cannot exist in the class hierarchy. - By adding class
that inherits the class hierarchy remains in order, that is, not a single diamond is formed.
Write a programme that will process the declarations respectively as described above and determine the correctness of each one of them.
Input Specification
The first line of input contains the integer K : P1 P2 ... Pk ;
where :
and ;
) are separated by exactly one space. In each specific declaration, for the number of classes
Output Specification
You must output ok
if the greska
if it isn't.
Constraints
Subtask | Score | Constraints |
---|---|---|
Sample Input 1
10
shape : ;
rectangle : shape ;
circle : shape ;
circle : ;
square : shape rectangle ;
runnable : object ;
object : ;
runnable : object shape ;
thread : runnable ;
applet : square thread ;
Sample Output 1
ok
ok
ok
greska
ok
greska
ok
ok
ok
greska
Explanation for Sample Output 1
- The fourth declaration is incorrect because class
circle
has already been defined in the third row. - The sixth declaration is incorrect because class
object
hasn't been defined yet. - The eighth declaration is correct because class
object
has now been declared, and the sixth declaration was discarded, so classrunnable
hasn't been defined yet. - The tenth declaration is incorrect because otherwise the following diamond forms:
shape
,applet
,square
,runnable
.
Sample Input 2
9
a : ;
x : ;
b : a x ;
c : b ;
d : a b c ;
e : d a ;
f : c e ;
y : x ;
g : c y e ;
Sample Output 2
ok
ok
ok
ok
ok
ok
ok
ok
greska
Explanation for Sample Output 2
- The tenth declaration is incorrect because otherwise the following diamond forms:
x
,g
,y
,d
(and many others).
Comments