Συνδεδεμένες Πόλεις

Ο Pak Dengklek ζει στην Ινδονησία, μια χώρα που αποτελείται από ~N~ πόλεις με αριθμό από ~0~ έως ~N - 1~. Για Κάθε ζευγάρι πόλεων, υπάρχει μονόδρομος που πηγαίνει από τη μια πόλη στην άλλη. Ο Pak Dengklek δεν έχει πληροφορίες για την κατεύθυνση των δρόμων, αλλά ο Pak Chanek προσφέρθηκε να τον βοηθήσει.

Ο Pak Dengklek επιτρέπεται να κάνει στον Pak Chanek το πολύ 40 000 ερωτήσεις. Για κάθε ερώτηση με τη σειρά, Ο Pak Dengklek διαλέγει ένα ζευγάρι πόλεων και ο Pak Chanek του λέει την κατεύθυνση του δρόμου που συνδέει αυτές τις δύο πόλεις.

Ο Pak Dengklek θέλει να μάθει έναν αριθμό πόλης με έναν το πολύ εξερχόμενο δρόμο ή να αναφέρει εάν δεν υπάρχει μία τέτοια πόλη. Εάν υπάρχουν περισσότερες από μία τέτοιες πόλεις, ο Pak Dengklek χρειάζεται να γνωρίζει έναν τέτοιο αριθμό πόλης.

Λεπτομέρειες Υλοποίησης

Θα πρέπει να εφαρμόσετε την παρακάτω διαδικασία:

int find_town(int N)

• ~N~ : ο αριθμός των πόλεων στην Ινδονησία.
• Αυτή η διαδικασία θα πρέπει να επιστρέψει οποιονδήποτε αριθμό πόλης με το πολύ έναν εξερχόμενο δρόμο ή -1 εάν δεν υπάρχει τέτοια πόλη.
• Αυτή η διαδικασία καλείται ακριβώς μία φορά.

Η παραπάνω διαδικασία μπορεί να πραγματοποιήσει κλήσεις στην ακόλουθη διαδικασία:

bool check_road(int A, int B)

• ~A~, ~B~ : ένα ζευγάρι αριθμών πόλης που θα ζητηθεί στον Pak Chanek.
• Τα ~A~ και ~B~ πρέπει να είναι διακριτοί ακέραιοι από ~0~ έως ~N - 1~ συμπεριλαμβανομένου.
• Η διαδικασία επιστρέφει true αν υπάρχει δρόμος που πηγαίνει από την πόλη ~A~ στην πόλη ~B~ και επιστρέφει false εάν υπάρχει δρόμος που οδηγεί από την πόλη ~B~ στην πόλη ~A~.
• Αυτή η διαδικασία μπορεί να κληθεί το πολύ 40 000 φορές.

Παράδειγμα

Παράδειγμα 1

Σκεφτείτε ένα σενάριο στο οποίο υπάρχουν 3 πόλεις και οι δρόμοι που συνδέουν τις πόλεις απεικονίζονται από την παρακάτω εικόνα:

Η διαδικασία find_town καλείται με τον ακόλουθο τρόπο:

find_town(3)

Αυτή η διαδικασία μπορεί να καλέσει check_road(0, 1), η οποία (σε αυτό το σενάριο) επιστρέφει true. Σε αυτό το σημείο, υπάρχουν επαρκείς πληροφορίες για να συμπεράνουμε ότι η πόλη 1 έχει το πολύ έναν εξερχόμενο δρόμο. Επομένως, η διαδικασία μπορεί να επιστρέψει 1.

Επιπλέον, αυτή η διαδικασία μπορεί να καλέσει check_road(2, 1), η οποία (σε αυτό το σενάριο) επιστρέφει false. Σε αυτό το σημείο, υπάρχουν επαρκείς πληροφορίες για να συμπεράνουμε ότι η πόλη 2 έχει το πολύ έναν εξερχόμενο δρόμος. Επομένως, η διαδικασία μπορεί επίσης να επιστρέψει 2.

Παράδειγμα 2

Σκεφτείτε ένα σενάριο στο οποίο υπάρχουν 5 πόλεις και οι δρόμοι που συνδέουν τις πόλεις απεικονίζονται από την παρακάτω εικόνα:

Η διαδικασία find_town καλείται με τον ακόλουθο τρόπο:

find_town(5)

Σε αυτό το σενάριο, δεν υπάρχει πόλη με το πολύ έναν εξερχόμενο δρόμο. Επομένως, η διαδικασία θα πρέπει να επιστρέψει -1.

Περιορισμοί

• ~3 \le N \le 2000~

Υποπροβλήματα

1. (10 βαθμοί) ~N \le 250~
2. (90 βαθμοί) Χωρίς πρόσθετους περιορισμούς.

Στο υποπρόβλημα 2 μπορείτε να λάβετε μερική βαθμολογία. Έστω ~Q~ ο μέγιστος αριθμός κλήσεων της διαδικασίας check_road σε όλες τις δοκιμαστικές περιπτώσεις σε αυτό το υποπρόβλημα. Η βαθμολογία σας για αυτό το υποπρόβλημα υπολογίζεται σύμφωνα με τον παρακάτω πίνακα:

Κατάσταση	Πόντοι
~20\, 000 < Q \le 40\, 000~	~20~
~8000 < Q \le 20\, 000~	~90-70 \sqrt{\frac{Q-100}{12000}}~
~Q < 8000~	~90~

Βαθμολόγηση

Σε ορισμένες περιπτώσεις δοκιμής, η συμπεριφορά του βαθμολογητή είναι προσαρμοστική. Αυτό σημαίνει ότι σε αυτές τις δοκιμαστικές περιπτώσεις ο βαθμολογητής δεν έχει σταθερή διαμόρφωση των κατευθύνσεων του δρόμου. Αντίθετα, οι απαντήσεις που δόθηκαν από το βαθμολογητή μπορεί να εξαρτώνται από τις ερωτήσεις που θέτει η λύση σας. Είναι εγγυημένο ότι ο βαθμολογητής απαντάει με τέτοιο τρόπο ώστε μετά από κάθε απάντηση να υπάρχει τουλάχιστον μία διαμόρφωση των κατευθύνσεων του δρόμου συνεπή με όλες τις απαντήσεις που έχουν δοθεί μέχρι τώρα.

Υπόδειγμα βαθμολογητή

Ο βαθμολογητής δείγματος διαβάζει έναν πίνακα ~R~ με ~N~ συμβολοσειρές με ~N~ χαρακτήρες που αντιπροσωπεύουν τους δρόμους στην Ινδονησία. Για κάθε ~i~ και ~j~ έτσι ώστε ~0 \le i, j \le N - 1~ ~(i \neq j )~, ~R[i][j]~ είναι 1 αν υπάρχει δρόμος από την πόλη ~i~ στην πόλη ~j~ και το ~R[i][j]~ είναι 0 εάν υπάρχει δρόμος που πηγαίνει από την πόλη ~j~ στην πόλη ~i~. Για κάθε ~i~ έτσι ώστε ~0 \le i \le N - 1~, το ~R[i][i]~ θα πρέπει να είναι 0.

Ο βαθμολογητής δείγματος διαβάζει την είσοδο στην ακόλουθη μορφή:

• γραμμή ~1~: \(Ν\)
• γραμμή ~2 + i~ ~(0 \le i \le N - 1)~: ~R[i]~ Εάν ο βαθμολογητής δείγματος εντοπίσει παραβίαση πρωτοκόλλου, η έξοδος του βαθμολογητή δείγματος είναι Protocol Violation: <MSG>, όπου <MSG> είναι ένα από τα ακόλουθα:
• too many questions: η check_road καλείται περισσότερες από 40 000 φορές.
• invalid parameters: η check_road καλείται με το \(Α\) και \(Β\) να μην είναι διακριτοί ακέραιοι από ~0~ έως ~N - 1~ συμπεριλαμβανομένου.

Διαφορετικά, η έξοδος του βαθμολογητή δείγματος έχει την ακόλουθη μορφή:

• γραμμή 1: η επιστρεφόμενη τιμή της find_town.
• γραμμή 2: ο αριθμός των κλήσεων προς check_road.

Σημειώστε ότι ο βαθμολογητής δείγματος δεν είναι προσαρμοστικός.