Чимбулак#7471

Чимбулак

1 секунда

128 мегабайтів

Складна

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

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

Під місцями, що знаходяться одне від одного далі за всіх, розуміються такі пари, між якими найкоротша відстань (в кількості доріжок) максимальна. У відповіді потрібно вказати сумарну кількість найкоротших шляхів між усіма такими парами.

Вхідні дані

У першому рядку задано число $n (3 \leq n \leq 200, 000)$ n~(3 \le n \le 200,000). В кожному з наступних $n$ рядків міститься по два цілих числа — номери місць відпочинку, які з'єднує відповідна доріжка. Гарантується, що кожна доріжка з'єднує різні пари місць і що з будь-якого місця можна дістатися в будь-яке інше.

Вихідні дані

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

Приклади

У першому прикладі найбільш віддалені одне від одного місця — це пари $(1, 5)$ та $(1, 6)$ . Між кожною з цих пар існує по два різних найкоротших шляхи, тому відповідь — $4$ .

Приклад 1

Приклад 2