Стажировка в большой четвёрке

После окончания одной московской школы четырём лучшим ученикам предлагают стажировки в компаниях большой четвёрки (1 место в каждой компании). Стажировка компаний $A$ и $B$ пройдёт в Лондоне, а $C$ и $D$ — в Амстердаме. Директорке предстоит сложное задание: нужно распределить учеников по компаниям таким образом, чтобы распределение было стабильным. Хорошо, что она знает про алгоритм Гейла-Шепли, который строит устойчивое паросочетание.

Но есть проблема: из четырёх лучших выпускников Лина дружит с Ликой настолько сильно, что они не готовы ехать в разные места. Если их распределят в разные города, то они будут готовы отказаться от более предпочтительных стажировок, чтобы поехать вместе. Это стало вызовом для директорки: возможно ли теперь построить устойчивое паросочетание для любых предпочтений студентов и компаний?