다이아몬드 상속

C++과 비슷한 객체 지향 언어의 클래스 선언을 살펴본다. 선언은 모두 K : P1 P2 ... Pk ; 꼴이며, $K$는 새로 선언하는 클래스의 이름이고 $P_1, P_2, \dots, P_k$는 클래스 $K$가 상속하는 클래스의 이름이다. 예를 들어 shape : ;는 아무 클래스도 상속하지 않는 클래스 shape의 선언이고, square : shape rectangle ;은 클래스 shape와 rectangle을 상속하는 클래스 square의 선언이다.

클래스 $K_1$이 $K_2$를 상속하고, $K_2$가 $K_3$을 상속하고, 같은 식으로 $K_{m-1}$이 $K_m$을 상속하면, 클래스 $K_1, K_2, \dots, K_{m-1}$은 모두 클래스 $K_m$에서 파생되었다고 한다. 이 언어의 규칙은 순환 정의를 금지하므로 자기 자신에서 파생된 클래스는 있을 수 없다. 즉 클래스 계층은 방향 비순환 그래프를 이룬다. 계층에 다이아몬드가 나타나는 것도 금지된다. 다이아몬드는 다음 세 조건을 만족하는 서로 다른 네 클래스 $A$, $B$, $X$, $Y$를 말한다.

• 클래스 $X$와 $Y$는 클래스 $A$에서 파생되었다.
• 클래스 $B$는 클래스 $X$에서도 파생되었고 클래스 $Y$에서도 파생되었다.
• 클래스 $X$는 $Y$에서 파생되지 않았고, 클래스 $Y$도 $X$에서 파생되지 않았다.

그림 1: 다이아몬드

그림 2: 첫 번째 예제의 선언을 모두 처리한 뒤의 계층

선언 $n$개를 주어진 순서대로 처리하면서 각 선언이 올바른지 판정한다. 올바른 선언은 계층에 추가하고, 잘못된 선언은 버린다. 선언 K : P1 P2 ... Pk ;는 다음 세 조건을 모두 만족할 때 올바르다.

1. 클래스 $K$가 아직 선언되지 않았다.
2. 클래스 $P_1, P_2, \dots, P_k$가 모두 앞에서 이미 선언되었다. 이 조건 때문에 어떤 클래스도 자기 자신에서 파생될 수 없고, 계층에 순환도 생기지 않는다.
3. 클래스 $P_1, P_2, \dots, P_k$를 상속하는 클래스 $K$를 추가해도 계층이 규칙을 지킨다. 즉 다이아몬드가 하나도 생기지 않는다.

선언을 위와 같이 차례로 처리해 각 선언의 정확성을 판정하는 프로그램을 작성하시오.

첫째 줄에 선언의 개수 $n$이 주어진다. ($1 \le n \le 1\,000$)

다음 $n$개 줄에 선언이 한 줄에 하나씩 K : P1 P2 ... Pk ; 꼴로 주어진다. $P_1, P_2, \dots, P_k$는 클래스 $K$가 상속하는 클래스의 목록이고, 개수가 0개일 수도 있다. 한 선언에 등장하는 이름 $K, P_1, P_2, \dots, P_k$는 모두 서로 다르다. 클래스 이름은 길이가 10 이하인 영어 소문자 문자열이다. 선언을 이루는 각 요소(클래스 이름과 문자 :, ;)는 정확히 공백 한 개로 구분된다. 각 선언에서 상속하는 클래스의 개수 $k$는 $0 \le k \le 1\,000$을 만족한다.

$n$개 줄을 출력한다. $i$번째 줄에는 $i$번째 선언이 올바르면 ok를, 올바르지 않으면 greska를 출력한다.

첫 번째 예제

• 네 번째 선언은 클래스 circle이 세 번째 줄에서 이미 정의되었으므로 잘못되었다.
• 여섯 번째 선언은 클래스 object가 아직 정의되지 않았으므로 잘못되었다.
• 여덟 번째 선언은 올바르다. 이제 클래스 object가 선언되었고, 여섯 번째 선언은 버려졌으므로 클래스 runnable은 아직 정의되지 않은 상태다.
• 열 번째 선언은 잘못되었다. 추가하면 클래스 shape, applet, square, runnable이 다이아몬드를 이룬다.

두 번째 예제

• 마지막 선언은 잘못되었다. 추가하면 클래스 x, g, y, d가 다이아몬드를 이룬다. 이 밖에도 여러 다이아몬드가 함께 생긴다.