Как вы знаете, Васин брат живет во Флатландии. Во Флатландии n городов, соединенных n - 1 двусторонней дорогой. Города пронумерованы от 1 до n. Из любого города можно добраться до любого другого двигаясь по дорогам.
Компания «Два пути», в которой работает Васин брат, выиграла тендер на ремонт двух путей во Флатландии. Путем называется последовательность различных городов, последовательно соединенных дорогами. Пути, которые надо отремонтировать, компания может выбрать самостоятельно. Единственное условие, накладываемое тендером — они не должны пересекаться (то есть иметь общих городов).
Известно, что прибыль, которую получит компания «Два пути», равна произведению длин выбранных двух путей. Считая длину каждой дороги равной 1, а длину пути равной количеству дорог в ней, найдите максимальную возможную прибыль компании.