Hay $n$ ciudades, $2$ compañías aéreas en un país. Entre dos ciudades cualesquiera, hay exactamente un vuelo de $2$ vías que las conecta y que es operado por una de las dos compañías. Una matemática planea una ruta de viaje, de modo que comience y termine en la misma ciudad, pase por al menos otras dos ciudades, y cada ciudad de la ruta sea visitada una vez. Ella descubre que dondequiera que empiece y cualquiera que sea la ruta que elija, debe tomar vuelos de ambas compañías. Encuentre el valor máximo de $n$.