42nd Balkan Mathematical Olympiad (BMO 2025 )

Problem 4.
There are $n$ cities in a country, where $n \geq 100$ is an integer. Some pairs of cities are connected by direct (two-way) flights. For two cities $A$ and $B$ we define:

$(i)$ A $\emph{path}$ between $A$ and $B$ as a sequence of distinct cities $A = C_0, C_1, \dots, C_k, C_{k+1} = B$ , $k \geq 0$ , such that there are direct flights between $C_i$ and $C_{i+1}$ for every $0 \leq i \leq k$ ;
$(ii)$ A $\emph{long path}$ between $A$ and $B$ as a path between $A$ and $B$ such that no other path between $A$ and $B$ has more cities;
$(iii)$ A $\emph{short path}$ between $A$ and $B$ as a path between $A$ and $B$ such that no other path between $A$ and $B$ has fewer cities.
Assume that for any pair of cities $A$ and $B$ in the country, there exist a long path and a short path between them that have no cities in common (except $A$ and $B$ ). Let $F$ be the total number of pairs of cities in the country that are connected by direct flights. In terms of $n$ , find all possible values $F$