Problem F
Hugga träd

Efter många år av forskning har Lolle äntligen motbevisat Lalexanders hypotes (denna hävdade att $(a+b)^2=a^2+b^2$). Nu känner sig Lolle färdig med sin matematiska karriär och drar sig tillbaka till skogen. En gång i veckan går han ut och hugger ned träd för virke. Lolle valde att flytta till en väldigt särskild skog: i denna skog består alla träd av $N$ knölar numrerade mellan $1$ och $N$, som kopplas samman av $N-1$ grenar. Självklart hålls träden ihop av grenarna, det vill säga är alla par av knölar indirekt sammankopplade av en eller fler grenar. Även om alla träd har lika många knölar kan de vara sammankopplade på olika sätt, vilket alltid gör det till en utmaning att hugga ner dem på ett effektivt vis.

Lolle vill nu ta hem ett särskilt träd. Varje knöl har bark på sig. För att kunna använda trädet behöver han skala av barken från varje knöl och ta bort alla grenar. För att skala knölar och ta bort grenar kan han utföra en huggning. För att utföra en huggning väljer han två knölar $a$ och $b$ som inte nödvändigtvis är närliggande. För varje knöl mellan $a$ och $b$ (inklusive $a$ och $b$) skalar han knölen och hugger sedan loss alla grenar som sitter fast på knölen. När grenarna huggs av kommer trädet delas upp i mindre sammanhängande träd. Han kan sedan utföra huggningar i dessa mindre träd. Notera att han endast kan välja två ändpunkter för en huggning om de är sammankopplade genom en väg av en eller flera grenar.

Eftersom Lolle inte är så sugen på att göra matte längre vill han ha hjälp med att hitta minsta antalet huggningar som han behöver utföra för skala alla knölar och ta bort alla grenar.

Indata

Den första raden innehåller heltalet $N$ ($1 \leq N \leq 10^5$), antalet knölar som trädet består av.

Därefter följer $N-1$ rader som vardera innehåller heltalen $a$ och $b$ ($1 \leq a,b \leq N$). Detta innebär att det finns en gren mellan knölarna med nummer $a$ och $b$. Det är garanterat att varje knöl är indirekt sammankopplad med alla andra knölar genom en eller flera grenar.

Utdata

Skriv ut ett heltal: minsta antalet huggningar som Lolle behöver utföra för att skala alla knölar och ta bort alla grenar.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall 1:

Till en början ser trädet ut såhär.

Om Lolle gör en huggning där $a=1$ och $b=4$ är de ljusröda knölarna kommer alla rödmarkerade knölar huggas av, då kanterna mellan $1-2$, $2-3$ och $3-4$ huggs av.

De kvarvarande knölarna som inte huggits av är följande:

Han kan sedan hugga med längs knölarna $a=6$ och $b=7$, sådan att kanten mellan $6-5$ och $5-7$ huggs av.

Förklaring av exempelfall 2:

Även om det inte finns några grenar måste knöl nummer $1$ skalas. Han kan då utföra en huggning med $a=b=1$.

7
1 2
2 3
3 4
2 5
5 6
6 7

2

1

1