Чимбулак
На известном казахском курорте Чимбулак для туристов есть n привлекательных для отдыха мест, между которыми проложено n дорожек одинаковой длины. По каждой дорожке можно перемещаться в любую сторону. Дорожки устроены так, что из любого места можно добраться в любое другое, однако иногда для этого приходится делать слишком много перемещений. Прежде чем прокладывать новые дорожки, Администрация курорта хочет выяснить, сколько существует различных путей между всеми парами мест для отдыха, расположенными друг от друга дальше всего.
Под "местами, расположенными друг от друга дальше всего" следует понимать пары, кратчайшее расстояние между которыми максимально. В качестве ответа требуется посчитать суммарное количество кратчайших путей между всеми подобными парами мест.
Входные данные
В первой строке находится число n (3 ≤ n ≤ 200 000). В каждой из следующих n строк находятся 2 числа - номера мест отдыха, между которыми проложена соответствующая дорожка. Гарантируется, что все дорожки соединяют разные пары мест отдыха.
Выходные данные
Выведите одно число - количество кратчайших путей между всеми парами наиболее удаленных друг от друга мест для отдыха.