BALKAN-SL 2008 C2

In one of the countries, there are $n \geq 5$ cities operated by two airline companies. Every two cities are operated in both directions by at most one of the companies. The government introduced a restriction that all round trips that a company can offer should have atleast six cities. Prove that there are no more than $\lfloor \tfrac{n^2}{3} \rfloor$ flights offered by these companies.