Коба і бананове дерево

Ваш друг Коба — розумна мавпа, і він обожнює банани. Сьогодні вранці в джунглях він вирвав з коренем бананове дерево (Коба дуже сильний) і відніс його до свого лігва. Коба планує сьогодні три перекуси, тому він думає, як зрізати дві гілки дерева, щоб розділити його на три частини (Коба буде їсти банани з кожної частини за один перекус). Коба хоче, щоб різниця в кількості бананів між частиною з найбільшою кількістю бананів і частиною з найменшою кількістю бананів була якомога меншою (Коба намагається дотримуватися збалансованої дієти). Такий розріз ми будемо називати оптимальним.

Бананове дерево, яке Коба приніс до свого лігва, є деревом, у вершинах якого знаходяться банани, пронумеровані від 1 до n. Дерево містить n − 1 гілку, які служать з'єднувальними ланками між цими бананами. Тобто банани є вершинами дерева, а гілки — ребрами.

Вам надано структуру дерева, яке Коба приніс до свого лігва. Виходячи з цього, знайдіть різницю в кількості бананів між частиною з найбільшою кількістю бананів і частиною з найменшою кількістю бананів в оптимальному розрізі.

Вхідні дані

У першому рядку записано одне ціле число n (3 ≤ n ≤ 2 * 10^5) — кількість бананів. У кожному з наступних n - 1 рядків записано по два цілих числа u[i], v[i] (1 ≤ u[i], v[i] ≤ n) — пари бананів, з'єднаних гілкою (ребром).

Вихідні дані

Виведіть одне ціле число — різницю в кількості бананів між частиною з найбільшою кількістю бананів і частиною з найменшою кількістю бананів в оптимальному розрізі.

Приклади

Примітка

Приклад 1. Якщо ми обріжемо гілки між 2 і 3, 4 і 5, то дерево буде розділено на три частини розміром 2, 2 і 1. Відповідь 2 − 1 = 1.

Приклад 2. Оптимальні розрізи наведені на малюнку вище. Розміри частин, що утворюються в результаті розрізів, дорівнюють 4, 2 і 3. Відповідь 4 − 2 = 2.