Давным давно где-то в Азии в одной стране шли междоусобные войны.

Каждый из n городов хотел захватить власть, поэтому иногда один город собирал армию и отправлял ее в поход против другого города.

Прокладывание дорог было делом трудным, поэтому их в стране было мало, а именно n - 1. Также из любого города до любого другого можно было добраться по этим дорогам.

Даже во время войны жители Востока остаются людьми духовно богатыми и ценящими красоту природы. И, дабы оставить на века память о своем великом походе, на дороге, на которой в пути армия провела больше всего времени, сажали одно красивое дерево. Жители Востока любят природу, поэтому если таких дорог было несколько, то по одному дереву сажалось на каждой.

Недавно, когда были обнаружены летописи той войны, выяснилось, что каждый город напал на каждый ровно по одному разу. Всего было ровно n(n - 1) походов. Всем стало интересно, какая дорога после тех войн стала самой красивой, то есть на какой дороге посадили больше всего красивых деревьев.