El archipiélago de Imomi consta de $n\geq 2$ islas. Entre cada par de islas distintas hay una línea de ferry única que funciona en ambas direcciones, y cada línea de ferry es operada por una de las $k$ compañías. Se sabe que si alguna de las $k$ compañías cierra todas sus líneas de ferry, entonces se vuelve imposible para un viajero, sin importar dónde comience el viajero, visitar todas las islas exactamente una vez (en particular, no regresar a la isla donde comenzó el viajero). Determine el valor máximo posible de $k$ en términos de $n$ .