SPOJ in Armenian

Հայտնի ղազախական Չիմբուլակ առողջարանում տուրիստների համար կան N հանգստանալու համար գրավիչ վայրեր, որոնց միջև անց են կացված N  միևնույն երկարության ճանապարհներ։ Ճանապարհները երկկողմանի են։ Ճանապարհները կառուցված են այնպես, որ ցանկացած տեղից կարելի է հասնել ցանկացած տեղ, սակայն երբեմն դրա համար հարկ է լինում շատ տեղափոխություններ կատարել։ Նախքան նոր ճանապարհներ կառուցելը առողջարանի ղեկավարությունը ցանկանում է պարզել, թե իրարից ամենից հեռու գտնվող հանգստանալու համար նախատեսված բոլոր վայրերի զույգերի միջև քանի տարբեր երթուղիներ գոյություն ունեն։

“Իրարից ամենից հեռու գտնվող վայրեր” ասելով, պետք է հասկանալ այն զույգերը, որոնց միջև եղած հեռավորությունը մաքսիմալ է։ Հարկավոր է հաշվել այդպիսի վայրերի միջև կարճագույն երթուղիների քանակը։

Մուտք

Առաջին տողում տրված է N (3<=N<=200000) թիվը։ Հաջորդ N տողերից յուրաքանչյուրում տրված են 2 թվեր՝ հանգստի վայրերի համարները, որոնց միջև ճանապարհ կա։ Երաշխավորվում է, որ բոլոր ճանապարհները միացնում են տարբեր վայրեր։

Ելք

Արտածեք մի թիվ՝ իրարից առավել հեռու գտնվող բոլոր զույգերի միջև կարճագույն ճանապարհների քանակը։

Օրինակներ

Մուտք.
6
1 2
1 3
2 4
4 3
4 5
4 6

Ելք.
4

Մուտք.
4
1 2
1 3
1 4
4 3

Ելք.
2

Դիտողություն
Առաջին օրինակում իրարից առավել հեռացած վայրերն են 1, 5 և 1, 6 զույգերը։
 1-ից 5 երկու տարբեր կարճագույն ճանապարհ կա։ Նույնքան կա մյուս զույգի համար։ Դրա համար պատասխանը 4 է։