eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Чимбулак

Чимбулак

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

Под "местами, расположенными друг от друга дальше всего" следует понимать пары, кратчайшее расстояние между которыми максимально. В качестве ответа требуется посчитать суммарное количество кратчайших путей между всеми подобными парами мест.

Входные данные

В первой строке находится число n (3n200 000). В каждой из следующих n строк находятся 2 числа - номера мест отдыха, между которыми проложена соответствующая дорожка. Гарантируется, что все дорожки соединяют разные пары мест отдыха.

Выходные данные

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

Пример

Входные данные #1
6
1 2
1 3
2 4
4 3
4 5
4 6
Выходные данные #1
4
Входные данные #2
4
1 2
1 3
1 4
4 3
Выходные данные #2
2
Источник 2014 X Международная Жаутыковская Олимпиада Алматы, Казахстан, 12-18 января