Problem E
Kattriket

En kontinent består av $N$ olika stadsstater. Exakt $N - 1$ par av stadsstater är direkt sammankopplade med en handelsväg, på ett sådant sätt att det går att färdas mellan alla par av stadsstater längs en sekvens av handelsvägar.

Efter att stadsstaterna under århundraden levt i harmoni och fred råder det just nu starka spänningar mellan den största stadsstaten, Katen, och ett konkurrerande rike, Kattago. Katen planerar att snabbt erövra de övriga stadsstaterna för att förena dessa i sin kamp mot Kattago.

Katen ska nu utföra sitt första fälttåg och erövra ett antal stadsstater för att bilda en union. Unionen måste bestå av en sammanhängande mängd stadsstater och inkluderar alltid Katen. Med detta menas att det ska vara möjligt att färdas mellan varje stadsstat i unionen med hjälp av handelsvägarna utan att besöka en stadsstat utanför unionen. För att förenkla sin logistik i fälttåget vill de dock att antalet frontstater i unionen blir så litet som möjligt. En frontstat är en stadsstat som är direkt sammankopplad med exakt en annan stadsstat inom unionen. Katen räknas dock aldrig som en frontstat.

För varje antal stadsstater $1, 2, \dots , N-1$ som Katen kan erövra under ett fälttåg, kan du beräkna det minsta antalet frontstater i den resulterande unionen?

Indata

Den första raden innehåller heltalet $N$ ($2 \le N \le 100\, 000$), antalet stadsstater på kontinenten.

De följande $N - 1$ raderna beskriver handelsvägarna. Låt alla stadsstater vara numrerade $0$, $1$, $\dots $, $N - 1$, där Katen är stadsstat $0$. Varje rad innehåller två heltal $a$ och $b$ ($0 \le a, b < N$, $a \neq b$), namnen på två stadsstater som är direkt sammankopplade med en handelsväg.

Utdata

Skriv ut en rad med det minsta antalet frontstater i en union med $1$, $2$, $\dots $, $N - 1$ erövrade stadsstater.

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

I det första exemplet kan Katen erövra t.ex stadsstat $1$ och $3$ i ett fälttåg. Då är bara $3$ en frontstat, eftersom $1$ är direkt sammankopplad med både Katen och stadsstat $3$. När alla $3$ stadsstater erövrats blir dock både stadsstat $2$ och $3$ frontstater.

4
0 1
0 2
1 3

1 1 2

8
0 1
1 2
2 3
3 4
3 7
2 5
5 6

1 1 1 1 2 2 3