IMO олимпиада по математике 2020 года | Казахстанские олимпиады

Дано целое число $n > 1.$ На горном склоне расположено $n^2$ фуникулёрных станций на разных высотах. Каждая из двух фуникулёрных компаний $A$ и $B$ владеет $k$ подъёмниками. Каждый подъёмник осуществляет регулярный беспересадочный трансфер с одной из станций на другую, более высоко расположенную станцию. $k$ трансферов компании $A$ начинаются на $k$ различных станциях; также они заканчиваются на $k$ различных станциях; при этом трансфер, который начинается выше, и заканчивается выше. Те же условия выполнены для компании $B$. Будем говорить, что две станции связаны фуникулёрной компанией, если можно добраться из нижней станции в верхнюю, используя один или несколько трансферов данной компании (другие перемещения между станциями запрещены). Найдите наименьшее $k,$ при котором заведомо найдутся две станции, связанные обеими компаниями.