3 En el país hay $N$ ciudades y algunos pares de ciudades están conectados por aerolíneas de dos vías (cada par con no más de una). Cada aerolínea pertenece a una de $k$ compañías. Resulta que es posible llegar de cualquier ciudad a cualquier otra, pero esto falla cuando eliminamos todas las aerolíneas que pertenecen a cualquiera de las compañías. ¿Cuál es el número máximo posible de aerolíneas en el país?