IZHO 2014

На известном казахском курорте Чимбулак для туристов есть N привлекательных для отды-
ха мест, между которыми проложено N дорожек одинаковой длины. По каждой дорожке можно
перемещаться в любую сторону. Дорожки устроены так, что из любого места можно добраться в
любое другое, однако иногда для этого приходится делать слишком много перемещений. Прежде
чем прокладывать новые дорожки, Администрация курорта хочет выяснить, сколько существует
различных путей между всеми парами мест для отдыха, расположенными друг от друга дальше
всего.
Под "местами, расположенными друг от друга дальше всего," следует понимать пары, кратчай-
шее расстояние между которыми максимально. В качестве ответа требуется посчитать суммарное
количество кратчайших путей между всеми подобными парами мест.
Формат входного файла
В первой строке входного файла находится число N (3 ≤ N ≤ 200 000). В каждой из следующих
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. Между каждой
парой этих мест есть два различных пути, поэтому ответ на этот пример 4.
Для 30% баллов N ≤ 500.
Для 50% баллов N ≤ 5000.