Servade kustutamine

문제

Graafiteoorias nimetatakse puuks sidusat tsükliteta graafi. Leheks nimetatakse puu tippu, millest väljub ainult üks serv. Puud nimetatakse paarispuuks, kui ükski tee selle lehtede vahel ei koosne paaritust arvust servadest. Ka ühe tipu (ja null servaga) puu loetakse paarispuuks.

Kui puust mõni serv kustutada, saame mittesidusa graafi, mille iga sidususkomponent on omakorda puu. Selles ülesandes on antud puu $GG$ ja vaja on leida minimaalne hulk servi, mille eemaldamisega saame paarismetsa: graafi, mille kõik sidususkomponendid on paarispuud.

입력

Sisendi esimesel real on graafi $GG$ tippude arv $NN$ ($1\le N\le {10}^{6}1\; \backslash le\; N\; \backslash le\; 10^6$). Graafi tipud on nummerdatud $1\dots N1\; \backslash ldots\; N$. Järgmisel $N-1N\; -\; 1$ real on igaühel kaks tühikuga eraldatud täisarvu $U_{i}U\_i$ ja $V_{i}V\_i$ ($1\le U_i\le N1\; \backslash le\; U\_i\; \backslash le\; N$, $1\le V_i\le N1\; \backslash le\; V\_i\; \backslash le\; N$, $U_i\mathrm{\ne }{V}_{i}U\_i\; \backslash ne\; V\_i$), mis näitavad, et graafi tippude $U_{i}U\_i$ ja $V_{i}V\_i$ vahel on serv. Võib eeldada, et $GG$ on kindlasti puu.

출력

Väljundi ainsale reale väljastada täisarv $KK$, mis näitab, mitu serva on gaafist $GG$ vaja minimaalselt eemaldada, et saada paarismets.