Field Trip

Ως ξεχωριστό δώρο για την τάξη του νηπιαγωγείου σας, τους πηγαίνετε μια εκδρομή σε ένα μαγικό μέρος των θαυμάτων.

Η τάξη σας έχει ~N~ μαθητές, αριθμημένους από το ~1~ έως το ~N~ για ευκολία. Υπάρχουν ~M~ άμεσες, αμφίδρομες φιλίες που υπάρχουν μεταξύ των μαθητών. Κάθε μαθητής είναι φίλος με το πολύ δύο άλλους μαθητές.

Εκτός από τις ~M~ άμεσες φιλίες, οι μαθητές μπορούν επίσης να γνωριστούν μεταξύ τους. Δύο μαθητές ~i~ και ~j~ είναι γνωστοί αν είναι φίλοι ή αν υπάρχει τρίτος μαθητής ~k~ που είναι γνωστός και του μαθητή ~i~ και του ~j~. Για παράδειγμα, εάν τα (~1~, ~2~), (~2~, ~3~), (~3~, ~4~) και (~4~, ~5~) είναι ζεύγη μαθητών με άμεση φιλία, τότε το άτομο ~1~ και το άτομο ~5~ είναι γνωστοί.

Ετοιμάζεστε να παραγγείλετε λεωφορεία για την εκδρομή, αλλά υπάρχουν δύο ζητήματα. Πρώτον, η εταιρία μεταφοράς επιμένει ότι κάθε λεωφορείο που παραγγέλνετε πρέπει να γεμίζει ακριβώς στη χωρητικότητά του ~K~ μαθητών. Δεν θα σας επιτρέψουν να παραγγείλετε ένα λεωφορείο εάν σκοπεύετε να βάλετε λιγότερους από ~K~ μαθητές σε αυτό! Δεύτερον, οι μαθητές είναι επιλεκτικοί σχετικά με τις συνθήκες ταξιδιού τους. Κάθε μαθητής ~i~ θα αρνηθεί να μπω σε λεωφορείο εκτός εάν πληρούνται και οι δύο παρακάτω προϋποθέσεις:

1. Όλοι οι άλλοι μαθητές που επιβιβάζονται σε αυτό το λεωφορείο είναι γνωστοί του μαθητή ~i~.

2. Όλοι οι γνωστοί του μαθητή ~i~ επιβιβάζονται σε αυτό το λεωφορείο.

Δυστυχώς, φαίνεται ότι τελικά μπορεί να μην μπορείτε να φέρετε ολόκληρη την τάξη σας σε αυτή την εκδρομή. Ωστόσο, θα κάνετε ό,τι χρειάζεται για να πάρετε όσο το δυνατόν περισσότερους μαθητές στα λεωφορεία. Οπως φαίνεται, Το «ό,τι χρειαστεί» μπορεί να περιλαμβάνει τον τερματισμό μιας ή δύο φιλιών, για το γενικότερο καλό. Μπορεί να επιλέξετε να διακόψετε ~0~ ή περισσότερες από τις ~M~ φιλίες μεταξύ των μαθητών, κάτι που φυσικά θα έχει επίσης επίδραση στο ποιοί μαθητές γνωρίζονται μεταξύ τους.

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

Είσοδος

Η πρώτη γραμμή περιέχει τρεις, χωρισμένους με κενό, ακέραιους ~N~, ~M~ και ~K~ (~1 \le N \le 10^6~, ~0 \le M \le 10^6~, ~1 \le K \le N~).

Οι επόμενες ~M~ γραμμές περιέχουνπληροφορίες σχετικά με τις φιλίες. Δηλαδή, κάθε μία από τις ~M~ γραμμές περιέχει δύο, χωρισμένους με κενό, ακέραιους ~A_i~ και ~B_i~ (~1 \le i \le M~) που περιγράφει ότι οι μαθητές ~A_i~ και ~B_i~ είναι φίλοι (~1 \le A_i, B_i \le N~, ~A_i \ne B_i~). Σημειώστε ότι καμία φιλία δεν ορίζεται δύο φορές (δηλαδή, δεν υπάρχουν δύο ζευγάρια φιλίας που να είναι ίσα μεταξύ τους).

Βαθμολογία

Για ~3~ από τους ~25~ διαθέσιμους βαθμούς, ~N \le 1\,000~.

Έξοδος

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

Παράδειγμα

input

8 5 2
1 4
8 2
4 5
6 2
3 5

output

6 2

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

Αν οι φιλίες μεταξύ των ζευγαριών μαθητών (~8~, ~2~) και (~4~, ~5~) τερματιστούν, τότε ~3~ λεωφορεία μπορούν να γεμίσουν ως εξής:

• Λεωφορείο ~1~: Μαθητές ~1~ και ~4~
• Λεωφορείο ~2~: Μαθητές ~2~ και ~6~
• Λεωφορείο ~3~: Μαθητές ~3~ και ~5~