Поликарп приехал в Байтогорск, один из городов Берляндии, по распоряжению начальства. Его задача — проверка маршруток города.

Дорожная сеть общественного транспорта Байтогорска состоит из $$$N$$$ остановок и нескольких дорог с двусторонним движением, соединяющих их. Сеть примечательна тем, что между любыми двумя остановками существует единственный путь из дорог, по которому можно проехать от одной остановки к другой (в обоих направлениях). Все дороги имеют одинаковую длину; маршрутка преодолевает дорогу за одну минуту.

Так как Байтогорск очень развитый город, для каждой пары остановок существует своя компания, занимающаяся перевозкой пассажиров. Причём маршрутка совершает остановки только на конечных пунктах пути, пропуская остальные остановки, если таковые встречаются в пути. Поликарпу нужно проверить каждую компанию, проехав единожды на маршруте каждой из них, неважно в каком направлении.

Его сейчас интересует время, которое он проведёт сидя (или стоя) в маршрутках. Ему кажется, что это займёт много времени, посчитайте количество минут, которое необходимо для проезда на всех маршрутах Байтогорска, пока он морально готовится.