Krtica

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

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό ~N~ ~(1 \le N \le 300\,000)~, τον αριθμό των δωματίων. Τα δωμάτια είναι αριθμημένα από ~1~ έως ~N~.
Κάθε μία από τις επόμενες ~N-1~ γραμμές περιέχει δύο ακέραιους αριθμούς, τον αριθμό των δωματίων που συνδέει ένα τούνελ.

Έξοδος

Τυπώστε σε ξεχωριστές γραμμές, με τη σειρά:

• Την απόσταση μεταξύ των δύο πιο απομακρυσμένων δωματίων μετά την ανακατασκευή.
  
• Ένα ζεύγος ακεραίων που αντιπροσωπεύουν μια προηγουμένως υπάρχουσα σήραγγα, η οποία θα πρέπει να κλείσει.
  
• Ένα ζεύγος ακεραίων, τα δωμάτια μεταξύ των οποίων πρέπει να ανοίξει μια νέα σήραγγα.
  Σημείωση: Η λύση δεν θα είναι απαραίτητα μοναδική. Τυπώστε οποιοδήποτε σχέδιο ανακατασκευής που επιτυγχάνει τη μικρότερη απόσταση μεταξύ των δύο πιο απομακρυσμένων δωματίων.

Βαθμολογία

Στα αρχεία ελέγχου αξίας ~40~% των πόντων, το ~N~ θα είναι μικρότερο από ~30~.
Στα αρχεία ελέγχου αξίας ~70~% των πόντων, το ~N~ θα είναι μικρότερο από ~3\,000~.
Επιπλέον, εάν η πρώτη γραμμή της εξόδου σας είναι σωστή και οι άλλες δύο λείπουν ή είναι εσφαλμένες, θα λάβετε περίπου το ~70%~ της αξίας εκείνου του αρχείου ελέγχου.

Παραδείγματα

input

4
1 2
2 3
3 4

output

2
3 4
4 2

input

7
1 3
2 3
2 7
4 3
7 5
3 6

output

3
2 3
7 3