Bob möcüzələr ölkəsində

Zəncir, məlum olduğu kimi, bir-birinə bağlı halqalardan ibarətdir. Adətən bütün halqalar eyni forma və ölçüdə olur. Bob - dəmirçinin şagirdi, öz ilk iridium zəncirini düzəldir. O, zəncir yaratmaq üçün ənənəvi formulaya əməl edir. O deyir:

• Əgər zəncir hələ yoxdursa, bir halqa düzəldin və o, zəncirinizin bir hissəsi olacaq.

• Əgər artıq zəncirin bir hissəsi varsa, bir halqa daha düzəldin və onu zəncirdəki başqa bir halqaya birləşdirin.

Bob ilk halqanı düzəltdi. Sonra, hər dəfə yeni bir halqa düzəltdikdə, onu zəncirdəki başqa bir halqaya birləşdirirdi, məhz formula ona dediyi kimi.

O, işini bitirdikdə, yaratdığı obyektin adi zəncirə heç bənzəmədiyini başa düşdü. Zənciri düzəltməyə çalışarkən, bir neçə dəfə zəncirin uclarında olan kimi görünən iki halqanı götürüb onları mümkün qədər uzaqlaşdırmağa çalışdı. Amma düzəldilmiş hissədən müxtəlif yerlərdə asılan bir neçə "zəncir" hissəsi daha var idi.

Bob üçün aydın idi ki, onun işi hələ bitməyib və o, yaratdığı obyekti natamam zəncir adlandırmağa qərar verdi. Bir az daha düşündükdən sonra, Bob belə nəticəyə gəldi ki, bəzi halqaları qırmalı və onları natamam zəncirin qalan hissəsi ilə diqqətlə birləşdirməlidir ki, düz zəncir əldə etsin. Düz zəncirdə hər bir halqa yalnız iki başqa halqaya bağlıdır. Düz zəncir halqanı qırmadan bir neçə hissəyə bölünə bilməz.

İndi daha diqqətli olan Bob, sadə addımlarla irəliləyəcək. Bir addımda o, natamam zəncirdə başqa bir halqaya $B$ bağlı olan halqa $A$ seçəcək. Sonra o, $A$-nı qıracaq, onu $B$-dən ayıracaq və $A$-nı natamam zəncirdəki başqa bir halqaya, məsələn $C$-yə yenidən birləşdirəcək. Əgər $A$-ya əvvəlcə bağlı olan $B$-dən başqa halqalar varsa, Bob onları addım boyunca $A$-ya bağlı saxlayacaq.

Bobun düz zəncir əldə etmək üçün minimum neçə addım atmalıdır?

Giriş verilənləri

Birinci sətirdə bir tam ədəd $n(1\le n\le 3\cdot 10^5)$ — natamam zəncirdəki halqaların sayı verilir. Halqalar $1,2,...,n$ kimi işarələnir. Növbəti $n-1$ sətirdə natamam zəncirdə bağlı olan iki halqanın etiketlərini göstərən iki tam ədəd verilir. Bağlantılar təsadüfi qaydada verilmişdir. Natamam zəncirin yalnız bir bütöv təşkil etdiyi təmin edilir.

Çıxış verilənləri

Bobun natamam zəncirini düz zəncirə çevirmək üçün atmalı olduğu minimum addımların sayını çıxarın.

Nümunələr