Dijamant

Παρατηρούμε δηλώσεις τάξεων σε μια αντικειμενοστρεφή γλώσσα προγραμματισμού παρόμοια με τη ~C++~. Καθε δήλωση τάξης είναι της μορφής "~K : P_1 P_2 \ldots P_k ;~" όπου ~K~ είναι το όνομα της νέας τάξης που δηλώθηκε και ~P_1, P_2, \ldots , P_k~ τα ονόματα των τάξεων που κληρονομούνται από την τάξη ~K~. Για παράδειγμα, "shape :;"" είναι μια δήλωση τάξης "shape" που δεν κληρονομεί καμία άλλη τάξη, ενώ "square: shape rectangle ;" είναι μια δήλωση τάξης "square" που κληρονομεί τις τάξεις "shape" και "rectangle".
Εάν η τάξη ~K_1~ κληρονομεί την τάξη ~K_2~, η τάξη ~K_2~ κληρονομεί την τάξη ~K_3~ και ούτω καθεξής, μέχρι την κλάση ~K_{m-1}~ που κληρονομεί την κλάση ~K_m~ ,τότε λέμε ότι όλες οι τάξεις ~K_1, K_2, \ldots , K_{m-1}~ προέρχονται από την κλάση ~K_m~. Οι κανόνες της προγραμματιστικής γλώσσας απαγορεύουν τους κυκλικούς ορισμούς, επομένως δεν επιτρέπεται να υπάρχει τάξη που προέρχεται από τον εαυτό της. Με άλλα λόγια,η ιεραρχία της τάξης σχηματίζει ένα κατευθυνόμενο άκυκλο γράφημα. Επιπλέον, δεν επιτρέπεται για το λεγόμενο διαμάντι να εμφανίζεται στην ιεραρχία της τάξης. Ένα διαμάντι αποτελείται από τέσσερις διαφορετικές κατηγορίες ~A, B, X, Y~ έτσι ώστε να ισχύει:

• Οι τάξεις ~X~ και ~Y~ προέρχονται από το ~A~.
  
• Η τάξη ~B~ προέρχεται τόσο από το ~X~ όσο και από το ~Y~.
  
• Ούτε η τάξη ~X~ προέρχεται από το ~Y~ , ούτε η τάξη ~Y~ προέρχεται από το ~X~.

        Ένα διαμάντι            Η ιεραρχία μετά την επεξεργασία όλων των δηλώσεων
                      από το πρώτο παράδειγμα.

Σας δίνεται μια σειρά από δηλώσεις τάξεων που πρέπει να επεξεργαστείτε διαδοχικά και να καθορίσετε για κάθε μία αν έχει δηλωθεί σωστά. Οι σωστά δηλωμένες τάξεις προστίθενται στην ιεραρχία, ενώ οι λανθασμένες απορρίπτονται. Δήλωση "~K : P_1 P_2 \dots P_k ;~" δηλώνεται σωστά αν ισχύει το εξής:

1. Η τάξη ~K~ δεν έχει δηλωθεί ακόμα
   
2. Όλες οι τάξεις ~P_1, P_2 , . . . , P_k~ έχουν δηλωθεί προηγουμένως. Σημειώστε ότι αυτή η συνθήκη διασφαλίζει ότι τάξη δεν μπορεί ποτέ να προέλθει από τον εαυτό της ή ότι οι κύκλοι δεν μπορούν να υπάρχουν στην ιεραρχία της τάξης.
3. Προσθέτοντας κλάση ~K~ που κληρονομεί τα ~P_1 , P_2 , . . . , P_k~ η ιεραρχία της τάξης παραμένει σε τάξη, δηλαδή δε σχηματίζεται κανένα διαμάντι.

Γράψτε ένα πρόγραμμα που θα επεξεργάζεται τις δηλώσεις αντίστοιχα όπως περιγράφεται παραπάνω και θα προσδιορίζει την ορθότητα της κάθεμίας από αυτές.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο ~n~ - τον αριθμό των δηλώσεων.
Καθεμία από τις ακόλουθες ~n~ γραμμές περιέχει μια μόνο δήλωση με τη μορφή "~K:\,P_1\,P_2 \ldots P_k;~" όπου ~P_1,\,P_2, \ldots,\,P_k~ είναι μια σειρά από μηδέν, μία ή περισσότερες τάξεις που κληρονομεί η τάξη ~K~.
Όλα τα ονόματα τάξεων σε μια δήλωση ~K, P_1 , P_2, \ldots , P_k~ είναι αμοιβαία διαφορετικά.
Το όνομα κάθε τάξης είναι μια συμβολοσειρά το πολύ ~10~ πεζών γραμμάτων του αγγλικού αλφαβήτου.
Όλα τα στοιχεία μιας δήλωσης (τα ονόματα και οι χαρακτήρες τάξεων "~:~" και "~;~") χωρίζονται με ακριβώς ένα χώρο. Σε κάθε συγκεκριμένη δήλωση, για τον αριθμό των τάξεων ~k~ ισχύει ~0 \le k \le 1\,000~.

Έξοδος

Πρέπει να εκτυπώσετε ~n~ γραμμές. Η γραμμή ~i~ πρέπει να περιέχει "ok" εάν η δήλωση ~i~ είναι σωστή και "greska" εάν δεν είναι.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	13	~1 \le n \le 100~, η ορθότητα μπορεί να προσδιοριστεί ελέγχοντας μόνο τη συνθήκη ~1~.
2	14	~1 \le n \le 100~, η ορθότητα μπορεί να προσδιοριστεί ελέγχοντας μόνο τις συνθήκες ~1~ και ~2~.
3	29	~ 1 \le n \le 100~
4	44	~ 1 \le n \le 1\,000~

Παραδείγματα

input

10
shape : ;
rectangle : shape ;
circle : shape ;
circle : ;
square : shape rectangle ;
runnable : object ;
object : ;
runnable : object shape ;
thread : runnable ;
applet : square thread ;

output

ok
ok
ok
greska
ok
greska
ok
ok
ok
greska

Επεξήγηση του 1ου παραδείγματος:

• Η τέταρτη δήλωση είναι λανθασμένη επειδή η τάξη "circle" έχει ήδη οριστεί στην τρίτη σειρά.
• Η έκτη δήλωση είναι λανθασμένη επειδή η τάξη "object" δεν έχει οριστεί ακόμα.
• Η όγδοη δήλωση είναι σωστή γιατί η τάξη "object" έχει πλέον δηλωθεί και η έκτη δήλωση απορρίφθηκε, επομένως η τάξη "runnable" δεν έχει οριστεί ακόμα.
• Η δέκατη δήλωση είναι λανθασμένη γιατί διαφορετικά σχηματίζονται τα ακόλουθα διαμάντια: "shape", "applet", "square", "runnable".

input

9
a : ;
x : ;
b : a x ;
c : b ;
d : a b c ;
e : d a ;
f : c e ;
y : x ;
g : c y e ;

output

ok
ok
ok
ok
ok
ok
ok
ok
greska

Επεξήγηση του 2ου παραδείγματος:

*Η δέκατη δήλωση είναι λανθασμένη γιατί διαφορετικά σχηματίζονται τα ακόλουθα διαμάντια: "~x~", "~g~", "~y~", "~d~" (και πολλά άλλα).