PMO 2021 Problem 6

A certain country wishes to interconnect $2021$ cities with flight routes, which are always two-way, in the following manner:

• There is a way to travel between any two cities either via a direct flight or via a sequence of connecting flights.

• For every pair $(A, B)$ of cities that are connected by a direct flight, there is another city $C$ such that $(A, C)$ and $(B, C)$ are connected by direct flights.

Show that at least $3030$ flight routes are needed to satisfy the two requirements.