29871번 - 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 $G$ ja vaja on leida minimaalne hulk servi, mille eemaldamisega saame paarismetsa: graafi, mille kõik sidususkomponendid on paarispuud.

Sisendi esimesel real on graafi $G$ tippude arv $N$ ($1 \le N \le 10^6$). Graafi tipud on nummerdatud $1 \ldots N$. Järgmisel $N - 1$ real on igaühel kaks tühikuga eraldatud täisarvu $U_i$ ja $V_i$ ($1 \le U_i \le N$, $1 \le V_i \le N$, $U_i \ne V_i$), mis näitavad, et graafi tippude $U_i$ ja $V_i$ vahel on serv. Võib eeldada, et $G$ on kindlasti puu.

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