Ваш друг Коба — умная обезьяна, и он любит есть бананы. Он вырвал с корнем банановое дерево, которое нашел сегодня утром в джунглях (Коба очень сильный), и отнес его в свое логово. У Кобы сегодня будет три закуски. Поэтому он думает как срезать две ветки дерева чтобы разделить его на три части (Коба будет есть бананы с каждой из частей за один перекус). Коба хочет, чтобы разница в количестве бананов между частью с наибольшим количеством бананов и частью с наименьшим количеством бананов была как можно меньше (Коба старается придерживаться сбалансированной диеты). Будем называть такой разрез оптимальным.
Банановое дерево, которое Коба взял в свое логово, представляет собой дерево, в вершинах которого находятся бананы, пронумерованные с 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.