Qısa məsafələr ağacı

Verilmiş qeyri-yoğun ağac $n$ zirvədən ibarətdir. Qeyri-yoğun ağac — $n-1$ kənarı olan əlaqəli qrafdır.

Sizin vəzifəniz, zirvə $1$-dən istənilən digər zirvəyə qədər olan ən qısa yolun uzunluğu $2$-dən artıq olmaması üçün minimal sayda kənar əlavə etməkdir. Qeyd edin ki, döngələr və çoxlu kənarlar əlavə etmək icazəli deyil.

Giriş verilənləri

Birinci sətir ağacda olan zirvələrin sayını göstərən bir tam ədəd $n(2\le n\le 2\cdot 10^5)$ ehtiva edir.

Növbəti $n-1$ sətir kənarları təsvir edir: $i$-ci kənar $u_i,v_i(1\le u_i,v_i\le n)$ zirvələrinin cütü kimi verilir. Verilmiş qrafın ağac olduğu təmin edilir. Verilmiş kənarlar arasında döngələr və çoxlu kənarlar olmadığı təmin edilir.

Çıxış verilənləri

Bir tam ədəd çıxarın — zirvə $1$-dən istənilən digər zirvəyə qədər olan ən qısa yolun uzunluğu $2$-dən artıq olmaması üçün əlavə edilməli olan minimal kənarların sayı. Qeyd edin ki, döngələr və çoxlu kənarlar əlavə etmək icazəli deyil.

Nümunələr