JAG™ је нова револуционарна стратешка игра компаније “Најбољи лтд.”.

У игри постоји \(N\) територија. Неке две територије могу делити границу. Познато је да укупно \(N-1\) парова територија деле границу, на такав начин да су све територије повезане, тј. од било које територије је могуће доћи до било које друге, потенцијално прелазећи преко других територија.

Игру играју два играча, и на почетку партије они бирају своје територије. Територије бирају наизменично први па други играч. Свако од њих изабере тачно једну територију коју до сада ни један играч није изабрао. Ово се дешава све док постоји територија коју ни један играч није изабрао.

Раштрканост територија првог играча једнака је удаљености две његове најдаље територије (тачније броју граница преко којих је неопходно прећи на најкраћем путу између те две територије). Први играч жели да минимизује раштрканост својих територија, док други играч жели да максимизује тај број (раштрканост територија првог играча).

Исписати ову вредност при оптималној игри оба играча.

Опис улаза

У првом реду налази се број \(N\), број територија у игри. У наредних \(N-1\) редова налазе се по два броја \(u\) и \(v\), која означавају да \(u\) и \(v\) деле границу.

Опис излаза

У једином реду стандардног излаза исписати једну вредност, раштрканост територија првог играча при оптималној игри оба играча.

Пример 1

Улаз

5
1 2
1 3
1 4
1 5

Излаз

2

Пример 2

Улаз

4
1 2
2 3
3 4

Излаз

1

Објашњење примера 1

Како год да први играч игра, мора изабрати бар две територије из скупа \(\{2,3,4,5\}\). Између било које две од њих је растојање два.

Ограничења

• \(3 \leq N \leq 10^{5}\)
• \(1 \leq u, v \leq n\)

Тест примери су подељени у четири дисјунктне групе:

• У тест примерима вредним 20 поена: \(N \leq 10\).
• У тест примерима вредним 10 поена: Територије \(i\) и \(i+1\) деле границу, за свако \(i\) за које важи \(1 \leq i < N\).
• У тест примерима вредним 20 поена: \(N \leq 10^3\).
• У тест примерима вредним 50 поена: Нема додатних ограничења.