Ο Μίλτος το δελφίνι πήρε πρόσφατα προαγωγή και έγινε υπεύθυνος έκτακτων καταστάσεων ολόκληρου του Βυθού! Ως πρώτο του έργο ο αργηγός του Βυθού του ανέθεσε να φτιάξει ένα ολοκληρωμένο πλάνο δράσης σε περίπτωση συναγερμού για τσουνάμι. Ο Μίλτος ξέρει ότι πρέπει παρουσιάσει ένα πλάνο στο οποίο όλες οι πόλεις του Βυθού θα πρέπει να καταλήξουν σε μια συγκεκριμένη πόλη και από εκεί να κατευθυνθούν στο Μεγάλο καταφύγιο. Ο Μίλτος έχει μάθει από το σχολείο ότι ένα αποτελεσματικό πλάνο εκτάκτου ανάγκης ολοκληρώνεται σε βήματα για να μην δημιουργηθεί πανικός. Έτσι η κάθε πόλη επιτρέπεται να πάει σε πόλεις που θα ορίσει ο Μίλτος και από εκεί θα συνεχίσουν το ταξίδι τους για τον τελικό προορισμό. Ο Μίλτος επίσης ξέρει ότι δεν πρέπει να υπάρξει σε καμία περίπτωση κύκλος στο πλάνο γιατί θα δημιουργηθεί αμέσως πανικός και το όλο πλάνο θα αποτύχει. Ο Μίλτος έχει δημιουργήσει ένα πρόχειρο πλάνο στο οποίο όμως ενώ δεν υπάρχουν κύκλοι δεν είναι σίγουρος αν όλες οι πόλεις θα φτάσουν σε μια συγκεκριμένη πόλη! Για αυτό και ζητάει την βοήθεια σας!
Συγκεκριμένα σας δίνεται ο αριθμός Ν των πόλεων και ο αριθμός Μ των μονοπατιών που μπορούν να χρησιμοποιηθούν. Ο Μίλτος αναρωτιέται αν το πρόχειρο του πλάνο είναι έγκυρο και σας ζητάει να του πείτε την πόλη που θα μαζευτούν όλοι για να πάνε στο Μεγάλο Καταφύγιο.
Στην πρώτη γραμμή σας δίνονται οι αριθμοί Ν, Μ.
Ακολουθούν Μ γραμμές στις οποίες δίνονται δύο πόλεις (1<=v1,v2<=Ν).
Σε αυτήν την περίπτωση η πόλη v1 μπορεί να πάει στην πόλη v2. (Προσοχή! δεν ισχύει το αντίθετο η πόλη v2 δεν μπορεί να πάει στην v1)
Ένας αριθμός, η πόλη στην οποία θα φτάσουν όλες οι άλλες για να πάνε στο Μεγάλο καταφύγιο.
Αν δεν υπάρχει τέτοια πόλη τότε τυπώστε -1.
1<=Ν<=100000, 1<=Μ<=150000
6 6 1 4 2 4 4 5 5 6 4 6 3 6
6
Εαν σχεδιάσετε τον γράφο θα δείτε ότι όλες οι πόλεις μπορούν να καταλήξουν στην πόλη 6. Η πόλη 4 μπορεί είτε να πάει πρώτα στην πόλη 5 και μετά στην 6 είτε κατευθείαν στην 6. Ο τρόπος με τον οποίον θα φτάσουν στην τελική πόλη δεν έχει σημασία.
4 3 1 2 3 2 3 4
-1
Εαν σχεδιάσετε πάλι τον γράφο θα δείτε ότι δεν υπάρχει πόλη στην οποία όλες οι άλλες μπορούν να πάνε. Η πόλη 4 δεν μπορεί να πάει στην πόλη 2. Αν θέλαμε να το διορθώσουμε θα μπορούσαμε να βάλουμε μια ακμή από την πόλη 4 στην πόλη 2.
(Υπενθύμιση: Ο γράφος θα είναι πάντα ακυκλικός(δεν θα έχει κύκλους)).