BALKAN 2025 Problem 4

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

• a path between $A$ and $B$ as a sequence of distinct cities $A = C_{0}, C_{1}, \ldots , C_{k}, C_{k + 1} = B$ , $k \geqslant 0$ , such that there are direct flights between $C_{i}$ and $C_{i + 1}$ for every $0 \leqslant i \leqslant k$ ;- a 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;- a 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 of $F$ .