На відомому казахському курорті Чимбулак для туристів є n привабливих для відпочинку місць, між якими прокладено n доріжок однакової довжини. По кожній доріжці можна переміщатися в будь сторону. Доріжки влаштовані так, що з будь-якого місця можна дістатися в будь-яке інше, проте іноді для цього доводиться робити занадто багато переміщень. Перш ніж прокладати нові доріжки, Адміністрація курорту хоче з'ясувати, скільки існує різних шляхів між усіма парами місць для відпочинку, розташованими один від одного найдалі.

Під "місцями, розташованими один від одного sдалі всіх," слід розуміти пари, найкоротша відстань між якими максимальна. Потрібно порахувати сумарну кількість найкоротших шляхів між усіма подібними парами місць.

Вхідні дані

У першому рядку знаходиться число n (3 ≤ n ≤ 200 000). У кожному з наступних n рядків знаходяться 2 числа - номери місць відпочинку, між якими прокладена відповідна доріжка. Гарантується, що всі доріжки з'єднують різні пари місць відпочинку.

Вихідні дані

Виведіть одне число - кількість найкоротших шляхів між усіма парами найбільш віддалених один від одного місць для відпочинку.