1-я Европейская математическая олимпиада, Вильнос, Литва

Дано целое число $n \geqslant 2$. В Евроландии $n$ городов, причем любые два города соединены прямыми авиарейсами в обе стороны. Для каждой пары городов, император назначает положительную цену за авиарейс между городами, одинаковую для всех авиарейсов между выбранной парой городов. Для различных городов $A$ и $B$, пусть $D(A, B)$ обозначает количество авиарейсов в самом дешевом путешествии между городами; если таких путешествий несколько, то $D(A, B)$ выбирается по самому длинному путешествию. Для каждого значения $n$, найдите наибольшее возможное среднее значение $D(A, B)$ для всех пар различных городов $(A, B)$, которое император может достичь.