Narfouz у центрі#12438

Narfouz у центрі

2 секунди

256 мегабайтів

Складна

Як ми всі знаємо, Narfouz Al-Narfouz любить дратувати свою корову своїми задачами низької якості. Насправді, його корова вже готова відключити електрику в його квартирі!

Будинок, у якому живе Narfouz, має структуру дерева з $n$ квартирами та $n - 1$ n-1 коридорами.

Narfouz хоче виконати таку операцію рівно один раз:

Він видалить одну квартиру і всі коридори, з'єднані з нею, а потім переїде в один із центрів $^{⋆}$ \Large^{\star} однієї з компонент зв'язності, що залишилися.

Після виконання операції його корова перевірить кожну можливу квартиру, у якій він може жити, і відключить у ній електрику!

Narfouz нервово запитує вас: яка найбільша кількість можливих квартир може бути після одноразового виконання цієї операції?

$^{⋆}$ \Large^{\star} вершина в дереві вважається центром тоді й лише тоді, коли максимальна відстань від неї до будь-якої іншої вершини дерева є мінімальною серед усіх вершин

Вхідні дані

У першому рядку міститься ціле число $n$ $(3 \leq n \leq 2 \times 1 0^{5})$ (3 \leq n \leq 2 \times 10^5) — кількість квартир.

У $i + 1$ i+1-му рядку містяться два числа $u$ і $v$ $(1 \leq u, v \leq n)$ (1 \leq u,v \leq n), що позначають кінці $i$ -го коридору.

Вихідні дані

Виведіть одне ціле число — максимальну кількість можливих квартир, у яких Narfouz може жити після одноразового виконання операції.

Приклади

Приклад 1

Примітка

Після видалення $2_{nd}$ 2_{\mathsf{nd}} квартири ми отримаємо три компоненти зв'язності: ${4}$ , ${5}$ , ${1, 6, 7, 3}$ \{1,6,7,3\}

У першій компоненті зв'язності єдиним центром є $4$ .

У другій компоненті зв'язності єдиним центром є $5$ .

У третій компоненті зв'язності вершини $6$ і $7$ вважаються центрами.

Можна довести, що це єдиний оптимальний спосіб виконати операцію.

Оцінювання

Підзадача $1$ ( $25$ балів): $i$ -й коридор з'єднує квартири $1$ та $i + 1$ i+1
Підзадача $2$ ( $25$ балів): $i$ -й коридор з'єднує квартири $i$ та $i + 1$ i+1
Підзадача $3$ ( $100$ балів): $(1 \leq n \leq 1000)$ (1 \leq n \leq 1000)
Підзадача $4$ ( $200$ балів): Без додаткових обмежень