LHC

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

Έχετε ήδη πρόσβαση σε ένα εκτεταμένο δίκτυο από σήραγγες, το οποίο είναι εγγυημένο ότι είναι συνδεδεμένο και χωρίς κυκλικά μονοπάτια. Με άλλα λόγια, οι υπάρχουσες σήραγγες σχηματίζουν μια δομή δέντρου. Αυτό το σύστημα μπορεί να αντιπροσωπεύεται από ~N~ κόμβους, με σήμανση ~1~ έως ~N~ , συνδεδεμένους με ~N - 1~ σήραγγες, καθεμία από τις οποίες συνδέει δύο κόμβους. Οι σήραγγες μπορούν να διασχιστούν προς οποιαδήποτε κατεύθυνση (δηλαδή, εάν υπάρχει διασταύρωση από ~a~ στο ~b~, αυτή η διασταύρωση πηγαίνει επίσης από το ~b~ στο ~a~).

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

Για παράδειγμα, στο παρακάτω δίκτυο, μπορούμε να σχηματίσουμε έναν επιταχυντή μήκους ~4~ κατασκευάζοντας ένα τούνελ μεταξύ των κόμβων ~1~ και ~5~ ή μεταξύ ~2~ και ~5~:

Είσοδος

Η πρώτη γραμμή κάθε περίπτωσης δοκιμής θα περιέχει ~N~ (~3 \le N \le 400\,000~), τον αριθμό από κόμβους. Οι επόμενες ~N - 1~ γραμμές καθεμία θα περιέχουν δύο, χωρισμένους με κενό, ακέραιους ~i~ και ~j~, που υποδεικνύουν ότι υπάρχει μία σήραγγα μεταξύ των κόμβων ~i~ και ~j~ (~1 \le i, j \le N~).

Έξοδος

Η έξοδος θα πρέπει να αποτελείται από μία γραμμή με δύο, χωρισμένους με κενό, ακέραιους: το μήκος το μεγαλύτερου δυνατού επιταχυντή και τον αριθμό των τρόπων για να επιτύχουμε αυτό το μήκος. Σημειώστε ότι μπορεί να χρειαστείτε έναν ακέραιο ~64~ bit για να αποθηκεύσετε την απάντηση (long long στην C/C++, LongInt στην Pascal).

Βαθμολογία

Για τις περιπτώσεις δοκιμής αξίας 40% των βαθμών, μπορείτε να υποθέσετε ότι ~N \le 5\,000~.

Παράδειγμα

input

5
1 3
2 3
3 4
4 5

output

4 2