Решить задачу на перестановки

Есть 30 пар обуви (сапоги). Перемешали все 60 сапог между собой и поставили в ряд рандомно. Нужно их упорядочить так, чтобы каждый сапог нашел свою пару, при чем левый должен стоять слева, а правый - справа. При этом за один раз можно взять любых два сапога и поменять их местами. Вопрос: какое минимальное количество перестановок нужно сделать, чтобы получить ожидаемый результат?