На складе имеется 8 ящиков видов «A», «Б», «В», «Г», по два ящика каждого вида. Ящики распределены на 4 стопки, пронумерованные числами от 1 до 4. Как переставить ящики так, чтобы в каждой стопке были ящики одного вида?

На складе имеется 8 ящиков видов «A», «Б», «В», «Г», по два ящика каждого вида. Ящики распределены на 4 стопки, пронумерованные числами от 1 до 4. Первоначально в стопке 1 ящик A стоял на ящике В, в стопке 2 — ящик Б на ящике В, в стопке 3 — ящик A на ящике Г, в стопке 4 — ящик Б на ящике Г (см. рисунок).

Вам необходимо переставить ящики так, чтобы в каждой стопке были ящики одного вида (порядок неважен), например, все ящики вида А могут оказаться в стопке 2, все ящики вида Б — в стопке 4 и т.д.

При помощи погрузчика вы можете взять верхний ящик из одной стопки и поставить его поверх другой стопки. Например, если переставить ящик из стопки 1 в стопку 2, то получится следующее расположение:

Инструкцию для погрузчика будем записывать в виде двух чисел. Первое число — номер стопки, из которой берётся ящик, второе число — номер стопки, в которую перемещается ящик. Пример перемещения выше будет записываться как «1 2».

Одно перемещение выполняется за одну минуту, но у вас есть два погрузчика, и если они не мешают друг другу, то могут выполнять два перемещения одновременно.
У одновременно выполняемых перемещений все номера стопок (как начальных, так и конечных) должны быть различны. Например, можно одновременно выполнить перемещения «1 3» и «4 2», но нельзя одновременно выполнить перемещения «1 3» и «3 2», потому что стопка номер 3 участвует в каждом из этих перемещений.

Запишите последовательность перемещений, в результате выполнения которых ящики будут расставлены нужным образом. В каждой строке записывайте ровно одно перемещение (два числа), добавляя поля ввода по мере необходимости. Если два перемещения выполняются одновременно, они также записываются в двух соседних строках, например:

1 3
4 2

Вам необходимо переставить ящики нужным образом за минимальное время, количество перемещений минимизировать необязательно. Чем меньше времени будет требоваться вашему алгоритму для решения задачи, тем больше баллов вы получите.