В цій задачі скористаємося максимальним паросполученням.

Вершини в першій долі будуть позначати вертикалі, а в другій — горизонталі.

ROOKs будуть позначати ребра. ROOK, що розміщена в позиції ~(x_i, y_i)~, з'єднує ребром вершину ~x_i~ першої долі та ~y_i~ другої долі.

Оскільки в максимальному паросполученні одна вершина не може бути з'єднана з більше ніж одним ребром, на кожній вертикалі або горизонталі буде не більше однієї ROOK.

Варто зауважити, що в цій задачі хорошим рішенням є використати деякі оптимізації стосовно алгоритму куна:

Запускати пошук з половини, де є менше вершин.

Перед запуском основного алгоритму розставити деякі ребра жадно, а потім покращити рішення алгоритмом, це прискорить роботу алгоритму.