Ağacın boyanması

Sizə $n$ zirvədən ibarət olan bir ağac (istiqamətsiz əlaqəli aciklik qraf) verilib. Bu ağac üzərində bir oyun oynayırsınız.

Başlanğıcda bütün zirvələr ağ rəngdədir. Oyunun ilk gedişində bir zirvə seçib onu qara rəngə boyayırsınız. Sonrakı hər gedişdə, qara rəngli zirvələrdən biri ilə qonşu olan (kənar ilə birləşən) ağ rəngli bir zirvə seçib onu qara rəngə boyayırsınız.

Hər dəfə bir zirvə seçdiyinizdə (ilk gediş də daxil olmaqla), seçdiyiniz zirvəni ehtiva edən yalnız ağ zirvələrdən ibarət əlaqə komponentinin ölçüsünə bərabər olan xal alırsınız. Oyun bütün zirvələr qara rəngə boyandıqda sona çatır.

Aşağıdakı nümunəyə baxaq:

Zirvələr $1$ və $4$ artıq qara rəngə boyanıb. Əgər zirvə $2$ seçsəniz, $2,3,5$ və $6$ zirvələrindən ibarət əlaqə komponenti üçün $4$ xal alacaqsınız. Əgər zirvə $9$ seçsəniz, $7,8$ və $9$ zirvələrindən ibarət əlaqə komponenti üçün $3$ xal alacaqsınız.

Sizin məqsədiniz əldə edəcəyiniz xalların sayını maksimuma çatdırmaqdır.

Giriş verilənləri

Birinci sətir ağacdakı 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ətirin hər biri ağacın kənarını təsvir edir. $i$-ci kənar iki tam ədəd $u_i$ və $v_i(1\le u_i,v_i\le n,u_i\ne v_i)$ ilə təsvir olunur, bu kənarların birləşdirdiyi zirvələrin nömrələridir.

Verilmiş kənarların ağac təşkil etdiyi zəmanət verilir.

Çıxış verilənləri

Əgər optimal oynasanız, əldə edəcəyiniz maksimum xal sayını göstərən bir tam ədəd çıxarın.

Nümunələr