Çimqulaq#7471
Çimqulaq adlı məşhur qazax kurortunda mənzərəli istirahət yeri yerləşmişdir, bunların arasında hər iki istiqamətdə hərəkət etmək mümkündür və eyni uzunluqda olan yol vardır. Yol sistemi elə qurulub ki, hər hansı bir yerdən digər yerə gedə bilmək mümkündür. Lakin bəzi hallarda yol çox uzun ola bilər.
Yeni yollar çəkməzdən əvvəl, kurortun rəhbərliyi maksimum məsafədə olan istirahət yerləri arasında olan müxtəlif ən qısa yoların sayını müəyyən etmək istəyir.
Bir-birindən ən uzaqda olan yerlər, aralarında olan ən qısa məsafənin (yol sayı ilə) maksimum olduğu cütlər mənasında başa düşülür. Nəticədə, bu cütlərin arasındakı ən qısa yolların ümumi sayını göstərmək tələb olunur.
Birinci sətirdə n~(3 \le n \le 200,000) sayı verilmişdir. Sonrakı sətirin hər birində iki tam ədəd verilir — müvafiq yolu birləşdirən istirahət yerlərinin nömrələri. Hər bir yolun müxtəlif cüt yerləri birləşdirdiyi və hər hansı bir yerdən digərinə gedə bilmək mümkün olduğu zəmanət olunmuşdur.
Bir ədədi göstərin — bir-birindən ən uzaqlıqdakı istirahət yerləri arasında olan ən qısa yolların sayını göstərən ədəd.
Birinci nümunədə, ən uzaqda olan yerlər cütləridir: və . Bu cütlərin hər biri arasında iki fərqli ən qısa yol vardır, buna görə də cavab olacaqdır.
Nümunə 1
Nümunə 2