Фёдор выдвигается в президенты Байтландии! На дебатах (да-да!) его, конечно же, спросят, как он собирается решать транспортную проблему Байтландии? Дело действительно непростое, так как транспортная система Байтландии сейчас представляет собой дерево (связный граф без циклов). В министерстве транспорта Байтландии команда Федора выяснила, что средств в казне хватит на постройку всего одной дополнительной дороги. На дебатах Фёдор собирается сказать, что построит эту дорогу так, чтобы в стране было как можно больше различных простых путей. Простой путь — это путь, который проходит через каждую вершину не более одного раза. (два простых пути называются различными, если различается множество ребер, в них входящих).

Однако наука Байтландии в упадке, и команде Фёдора не удалось найти ученых, которые быстро выяснят, а какого же максимальноого количества простых путей можно достичь добавлением в транспортную систему одного ребра? Поэтому он обратился к вам. Ответьте на этот вопрос.

Можно добавлять ребро между вершинами, между которыми оно уже есть, но нельзя добавлять петлю.

В этой задаче мы рассматриваем только простые пути длины хотя бы два.