Cable cars on the mountain

Soit $n > 1$ un entier. Il y a $n^2$ stations sur le versant d'une montagne, toutes à des altitudes différentes. Chacune des deux compagnies de téléphériques, $A$ et $B$, gère $k$ téléphériques ; chaque téléphérique permet de se déplacer d'une des stations vers une station plus élevée (sans arrêt intermédiaire). Les $k$ téléphériques de $A$ ont $k$ points de départ différents et $k$ points d'arrivée différents, et un téléphérique qui a un point de départ plus élevé a aussi un point d'arrivée plus élevé. Les mêmes conditions sont satisfaites pour $B$. On dit que deux stations sont reliées par une compagnie s'il est possible de partir de la station la plus basse et d'atteindre la plus élevée en utilisant un ou plusieurs téléphériques de cette compagnie (aucun autre mouvement entre les stations n'est autorisé).

Déterminer le plus petit entier strictement positif $k$ qui garantisse qu'il existe deux stations reliées par chacune des deux compagnies.