Papričice

Afrika paprika! – S.V.

Μετά από ένα κουραστικό πρωινό στον κήπο, ο κύριος Malnar αποφάσισε να ανταμείψει τον εαυτό του με αποξηραμένες καυτερές πιπεριές που καλλιεργούσε ο ίδιος. Έχει n πιπεριές, συνδεδεμένες με ~n - 1~ κομμάτια σπάγκου, έτσι ώστε κάθε δύο πιπεριές να συνδέονται με ένα κομμάτι σπάγκου. Τυπικά, σχηματίζουν ένα δέντρο. Ο κ. Malnar θα φτιάξει τρία μεσημεριανά γεύματα σήμερα. Για το σκοπό αυτό, θα κόψει δύο σπάγκους για να πάρει τρία μικρότερα τμήματα, ένα για κάθε μεσημεριανό γεύμα.

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

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο ~n~, τον αριθμό των πιπεριών. Οι πιπεριές επισημαίνονται με ακέραιους αριθμούς από το 1 έως το ~n~.

Κάθε μία από τις ακόλουθες ~n - 1~ γραμμές περιέχει δύο ακέραιους αριθμούς ~x~ και ~y\;(1 \le x, y \le n)~ – οι ετικέτες των πιπεριών που συνδέονται απευθείας με ένα κομμάτι σπάγκου.

Έξοδος

Εκτυπώστε την ελάχιστη δυνατή διαφορά μεταξύ των μεγεθών των τμημάτων.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	15	~3 \le n \le 200~
2	35	~3 \le n \le 2\,000~
3	60	~3 \le n \le 200\,000~

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

input

4
1 2
2 3
3 4

output

1

input

6
1 2
1 3
3 4
3 5
5 6

output

0

input

9
1 3
2 3
3 4
3 5
5 6
5 7
7 8
7 9

output

2

Επεξήγηση παραδειγμάτων:

Στο πρώτο παράδειγμα, καθένας από τους τρεις πιθανούς τρόπους κοπής των σπάγκων δίνει ένα τμήμα με δύο πιπεριές και δύο τμήματα, με μία πιπεριά το καθένα. Επομένως η απάντηση είναι ~2 - 1 = 1~.

Στο δεύτερο παράδειγμα, είναι δυνατό να λάβετε τρία συστατικά του ίδιου μεγέθους κόβοντας τον σπάγκο που συνδέει τις πιπεριές 1 και 3, καθώς και τις πιπεριές 3 και 5, οπότε η απάντηση είναι 0.

Οι βέλτιστες κοπές για το τρίτο παράδειγμα φαίνονται στο αρχικό σχήμα. Τα μεγέθη των συστατικών είναι 4, 2 και 3 και η απάντηση είναι ~4 - 2 = 2~.