CNI "Tudor Vianu" PreOJI, clasele Xl-Xll | Paprika

Cerință

A venit timpul ca domnul B să îșî culeagă ardeii uscați cu care să își poată prepara bine-cunoscuta paprika. El are $n$ ardei, conectați prin $n-1$ crengi, astfel încât se poate ajunge de la orice ardei la orice alt ardei printr-o serie de crengi. Formal, ardeii lui formează un arbore. Cum el are și alte treburi mai importante, domnul B nu vrea să piardă prea mult timp culegând ardei, așa că mai cheamă incă doi prieteni care să îl ajute. Fiind un om cinstit, el decide să împartă sarcinile cât mai corect. Pentru asta, el va tăia $2$ crengi și va repartiza fiecăruia dintre ei câte un subarbore din cei $3$ rămași, dar vrea să minimizeze diferența dintre mărimea celui mai mare si celui mai mic subarbore. Voi trebuie sa determinați această diferență minimă.

Date de intrare

Pe prima linie a fișierului de intrare paprika.in se găsește $n$, numarul de ardei.
Fiecare din următoarele $n-1$ linii conține $2$ întregi $x$ si $y$, care reprezintă etichetele a $2$ ardei care sunt conectați direct printr-o creangă.

Date de ieșire

Pe prima linie a fișierului de ieșire paprika.out se va găsi un singur număr întreg, diferența cerută.

Restricții și precizări

• $1 \leq n \leq 200 \ 000$
• $1 \leq x, y \leq n$

Exemplul 1

paprika.in

4
1 2
2 3
3 4

paprika.out

1

Explicație

Oricare din cele 3 moduri de a tăia crengile va rezulta într-o componentă cu doi ardei si două componente cu un ardei. Astfel, răspunsul este $2-1=1$

Exemplul 2

paprika.in

6
1 2
1 3
3 4
3 5
5 6

paprika.out

0

Explicație

Este posibil sa obținem trei componente de aceeași mărime dacă tăiem crengile care conectează ardeii $1$ si $3$, respectiv ardeii $3$ si $5$.