ICPC Ανατολικοκεντρικός ΒΑ Τοπικός Διαγωνισμός 2005, Πρόβλημα B

Η Ann Sister έχει μια υπηρεσία γενεαλογικής βάσης δεδομένων, η οποία διατηρεί το ιστορικό του οικογενειακού δέντρου για τους πελάτες της. Όταν οι πελάτες συνδέονται στο σύστημα, παρουσιάζονται με μια ποικιλία υπηρεσιών: αναζήτηση, εκτύπωση, ερωτήματα, κ.λπ. Ένα πρόσφατο ερώτημα που προέκυψε για το οποίο το σύστημα δεν ήταν αρκετά προετοιμασμένο ήταν το εξής: "Ποιο μέλος της οικογένειάς μου είχε τα περισσότερα εγγόνια;" Ο πελάτης που έκανε το ερώτημα έπρεπε τελικά να το απαντήσει κάνοντας χειροκίνητη αναζήτηση στη βάση δεδομένων του οικογενειακού της δέντρου. Η Άννα αποφάσισε να γραφτεί λογισμικό σε περίπτωση που αυτό το ερώτημα (ή παρόμοιο με αυτό που ζητά δισέγγονα, ή τρισέγγονα κ.λπ.) ερωτηθεί στο μέλλον.

Είσοδος

Η είσοδος θα αποτελείται από πολλαπλές περιπτώσεις δοκιμής. Η πρώτη γραμμή της εισόδου θα περιέχει έναν μόνο ακέραιο που δείχνει τον αριθμό των περιπτώσεων δοκιμής. Κάθε δοκιμαστική περίπτωση ξεκινά με μια γραμμή που περιέχει δύο θετικούς ακέραιους αριθμούς ~n~ και ~d~, όπου ~n~ υποδηλώνει τον αριθμό των γραμμών που πρέπει να ακολουθήσουν και περιέχουν πληροφορίες για το οικογενειακό δέντρο και ~d~ υποδεικνύει το συγκεκριμένο ερώτημα που τίθεται για το δέντρο: αν ~d = 1~, τότε μας ενδιαφέρουν πρόσωπα με τα περισσότερα παιδιά (1 γενιά μακριά), αν ~d = 2~, τότε μας ενδιαφέρουν τα άτομα με τα περισσότερα εγγόνια (2 γενιές μακριά) και ούτω καθεξής. Οι επόμενες ~n~ γραμμές είναι της μορφής

~name\;\; m\;\; dname_1\;\; dname_2\;\; \ldots\;\; dname_m~

όπου name είναι ένα από τα ονόματα των μελών της οικογένειας, το ~m~ είναι ο αριθμός των παιδιών του/της και ~dname_1~ με ~dname_m~ είναι τα ονόματα των παιδιών. Αυτές οι γραμμές θα δοθούν χωρίς ιδιαίτερη σειρά. Εσείς μπορεί να υποθέσει ότι όλες οι ~n~ γραμμές περιγράφουν ένα μοναδικό, συνδεδεμένο δέντρο. Δεν θα είναι περισσότερα από 1000 άτομα σε οποιοδήποτε δέντρο και όλα τα ονόματα θα έχουν το πολύ 10 χαρακτήρες.

Έξοδος

Για κάθε δοκιμαστική περίπτωση, εξάγετε τα τρία ονόματα με τον μεγαλύτερο αριθμό καθορισμένων απογόνων κατά σειρά αριθμών απογόνων. Εάν υπάρχουν ίσοι αριθμοί απογόνων, πληκτρολογήστε τα ονόματα με τον ίδιο αριθμό απογόνων με αλφαβητική σειρά. Τυπώστε λιγότερα από τρία ονόματα εάν υπάρχουν λιγότερα από τρία άτομα που ταιριάζουν με τα κριτήρια του προβλήματος (θα πρέπει να μην εκτυπώσετε το όνομα μέλους που έχει 0 από τους καθορισμένους απογόνους) και εκτυπώστε περισσότερους από τρεις εάν υπάρχουν ίσοι απόγονοι κοντά στο τέλος της λίστας. Εκτυπώστε κάθε όνομα ένα ανά γραμμή, ακολουθούμενο από ένα μόνο κενό και μετά τον αριθμό των καθορισμένων απογόνων. Η έξοδος για κάθε περίπτωση δοκιμής πρέπει να ξεκινά με τη γραμμή

Tree i:

όπου ~i~ είναι ο αριθμός περίπτωσης δοκιμής (ξεκινώντας από το 1). Διαχωρίστε την έξοδο για κάθε πρόβλημα με μια κενή γραμμή.

Παράδειγμα Εισόδου

3
8 2
Barney 2 Fred Ginger
Ingrid 1 Nolan
Cindy 1 Hal
Jeff 2 Oliva Peter
Don 2 Ingrid Jeff
Fred 1 Kathy
Andrea 4 Barney Cindy Don Eloise
Hal 2 Lionel Mary
6 1
Phillip 5 Jim Phil Jane Joe Paul
Jim 1 Jimmy
Phil 1 Philly
Jane 1 Janey
Joe 1 Joey
Paul 1 Pauly
6 2
Phillip 5 Jim Phil Jane Joe Paul
Jim 1 Jimmy
Phil 1 Philly
Jane 1 Janey
Joe 1 Joey
Paul 1 Pauly

Παράδειγμα Εξόδου

Tree 1:
Andrea 5
Don 3
Cindy 2

Tree 2:
Phillip 5
Jane 1
Jim 1
Joe 1
Paul 1
Phil 1

Tree 3:
Phillip 5