Torrent

Ο Mirko εργάζεται σε ένα κέντρο δεδομένων και η σημερινή αποστολή είναι να αντιγράψει ένα αρχείο μεγέθους ~1~ GiB σε ~n~ υπολογιστές. Οι υπολογιστές συμβολίζονται με ακέραιους από το ~1~ έως το ~n~ και συνδέονται έτσι ώστε να σχηματίζουν ένα λεγόμενο δέντρο. Ακριβέστερα, ~n - 1~ ζεύγη υπολογιστών συνδέονται απευθείας μέσω καλωδίου δικτύου με τρόπο που να υπάρχει μια μοναδική διαδρομή μεταξύ κάθε ζεύγους υπολογιστών.

Στο πρώτο παράδειγμα, παίρνει δύο λεπτά για το αρχείο να αντιγραφεί σε όλους τους υπολογιστές

Αρχικά, ο Mirko τοποθέτησε χειροκίνητα το αρχείο σε δύο διαφορετικούς υπολογιστές – τον υπολογιστή ~a~ και τον υπολογιστή ~b~ και τώρα γράφει εντολές που θα αντιγράψουν το αρχείο σε όλους τους άλλους υπολογιστές. Το αρχείο μπορεί να αντιγραφεί από τον υπολογιστή ~x~ στον υπολογιστή ~y~ μόνο εάν οι δύο υπολογιστές είναι απευθείας συνδεδεμένοι και η διαδικασία αντιγραφής διαρκεί ακριβώς ένα λεπτό. Ανά πάσα στιγμή, κάθε μεμονωμένος υπολογιστής μπορεί να συμμετάσχει το πολύ σε μία διαδικασία αντιγραφής, αλλά επιτρέπεται η αντιγραφή του αρχείου μεταξύ αυθαίρετα πολλών διαφορετικών ζευγών υπολογιστών στην ίδια στιγμή. Επομένως, όταν η διαδικασία αντιγραφής από τον υπολογιστή ~x~ στον υπολογιστή ~y~ τελειώνει, είναι δυνατό στο επόμενο λεπτό να αντιγράψετε το αρχείο από τον υπολογιστή ~x~ στον υπολογιστή ~w~ και από τον υπολογιστή ~y~ στον υπολογιστή ~z~.
Προσδιορίστε τον ελάχιστο χρόνο που χρειάζεται για να αντιγραφεί το αρχείο σε όλους τους υπολογιστές.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο ~n~ και δύο διαφορετικούς ακέραιους αριθμούς ~a~ και ~b (1 \le a, b \le n)~ - τον αριθμό υπολογιστών και τα ονόματα των υπολογιστών που περιέχουν ήδη το αρχείο. Καθεμία από τις ακόλουθες ~n - 1~ γραμμές περιέχει δύο διαφορετικούς ακέραιους ~x~ και ~y (1 \le x, y \le n)~ - οι ετικέτες των υπολογιστών που συνδέονται απευθείας μέσω καλώδιο δικτύου. Το δίκτυο υπολογιστών σχηματίζει ένα δέντρο, όπως περιγράφεται στην εργασία.

Έξοδος

Πρέπει να εκτυπώσετε τον απαιτούμενο ελάχιστο χρόνο σε λεπτά.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	31	~2 \le n \le 1\,000~
2	69	~1\,000 \le n \le 300\,000~

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

input

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

output

2

input

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

output

4

input

17 1 2
1 3
1 4
4 6
6 7
3 8
3 9
3 10
1 13
13 5
13 11
13 12
13 14
14 15
15 16
15 17
14 2

output

5

Απεικονίσεις του 2ου και του 3ου παραδείγματος