Градоначальник города Q недавно получил от руководства письмо о важности повышения рейтинга городов страны в связи с предстоящим годом «высоких рейтингов». На первом этапе необходимо выслать рейтинг города, вычисленный по новой методике, в столицу государства.

Мэр поручил аналитическому отделу рассчитать этот рейтинг.

В городе Q расположено N памятников архитектуры, которые пронумерованы от 1 до N и между собой связаны автобусными маршрутами. Известно, что таких маршрутов ровно N - 1 и они позволяют туристу проложить путь между любой парой памятников (возможно, с пересадками). Назовем «привлекательностью» пути от памятника A до памятника B функцию F(A, B) = D, где D – количество оплаченных автобусных маршрутов, необходимых для того, чтобы добраться от A до B.

Для привлечения большего числа туристов и, соответственно, повышения рейтинга мэр издал указ о том, что каждый второй маршрут на пути от некоторого памятника A до некоторого памятника B является бесплатным.

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