Diamond Inheritance

You are watching class declarations in an object oriented language similar to C++. Every declaration has the form K : P1 P2 ... Pk ;, where $K$ is the name of the new class and $P_1, P_2, \dots, P_k$ are the names of the classes that class $K$ inherits. For example, shape : ; declares a class shape that inherits no class, while square : shape rectangle ; declares a class square that inherits the classes shape and rectangle.

If class $K_1$ inherits $K_2$, class $K_2$ inherits $K_3$, and so on up to class $K_{m-1}$ that inherits $K_m$, then the classes $K_1, K_2, \dots, K_{m-1}$ are all derived from class $K_m$. The rules of the language forbid circular definitions, so no class is derived from itself. In other words, the class hierarchy is a directed acyclic graph. A diamond in the hierarchy is forbidden too. A diamond is a set of four different classes $A$, $B$, $X$, $Y$ that satisfies all of the following.

• Classes $X$ and $Y$ are derived from class $A$.
• Class $B$ is derived from class $X$ and also from class $Y$.
• Class $X$ is not derived from $Y$, and class $Y$ is not derived from $X$.

Figure 1: A diamond

Figure 2: The hierarchy after all declarations of the first example are processed

You are given $n$ declarations to process in the given order, and you decide for each one whether it is declared correctly. A correct declaration is added to the hierarchy, an incorrect one is discarded. The declaration K : P1 P2 ... Pk ; is correct when all of the following hold.

1. Class $K$ has not been declared yet.
2. Classes $P_1, P_2, \dots, P_k$ have all been declared earlier. Because of this condition no class can ever be derived from itself and no cycle can appear in the hierarchy.
3. Adding class $K$ that inherits $P_1, P_2, \dots, P_k$ keeps the hierarchy in order, that is, not a single diamond is formed.

Write a program that processes the declarations in order as described above and decides the correctness of each one.

The first line contains the integer $n$, the number of declarations ($1 \le n \le 1\,000$).

Each of the next $n$ lines contains a single declaration in the form K : P1 P2 ... Pk ;, where $P_1, P_2, \dots, P_k$ is a list of zero or more classes that class $K$ inherits. All names $K, P_1, P_2, \dots, P_k$ in a single declaration are different. Each class name is a string of at most 10 lowercase letters of the English alphabet. All elements of a declaration (the class names and the characters : and ;) are separated by exactly one space. In each declaration the number of inherited classes $k$ satisfies $0 \le k \le 1\,000$.

Output $n$ lines. The $i$th line contains ok if the $i$th declaration is correct, and greska if it is not.

The first example

• The fourth declaration is incorrect because class circle was already defined in the third line.
• The sixth declaration is incorrect because class object has not been defined yet.
• The eighth declaration is correct. Class object is declared by now, and the sixth declaration was discarded, so class runnable is still undefined.
• The tenth declaration is incorrect. Adding it makes the classes shape, applet, square, runnable form a diamond.

The second example

• The last declaration is incorrect. Adding it makes the classes x, g, y, d form a diamond. Several other diamonds appear along with it.