CGMO 2012 Problem 6

There are $n$ cities, $2$ airline companies in a country. Between any two cities, there is exactly one $2$ -way flight connecting them which is operated by one of the two companies. A female mathematician plans a travel route, so that it starts and ends at the same city, passes through at least two other cities, and each city in the route is visited once. She finds out that wherever she starts and whatever route she chooses, she must take flights of both companies. Find the maximum value of $n$ .