Имеется три стержня, на один из которых нанизано несколько дисков различного радиуса. Диски расположены так, что на диске с большим радиусом лежит диск с меньшим радиусом (такое правило должно сохраняться всегда). Известна задача «О ханойских башнях», в которой требуется переложить диски с одного стержня на другой оптимальным образом, т.е. за наименьшее число перекладываний.

Существует простое рекурсивное решение данной задачи: * Перекладываем верхние \(n\)-1 диск с начального на промежуточный стержень. * Перекладываем диск \(n\) на последний стержень. * Перекладываем \(n\)-1 диск с промежуточного на последний стержень.

Пример реализации алгоритма на языке Pascal:

Procedure move(n,s,t: integer);
Begin
  If n>1 then move(n-1,s,6-s-t);
  Writeln(s,t);
  If n>1 then move(n-1,6-s-t,t);
End;

а трех стержнях дана правильная раскладка \(N\) дисков (меньший диск лежит на большем). Вам нужно ответить на \(M\) запросов, каждый из которых состоит из двух целых чисел \(s\) и \(t\) – номера стержней. Для каждого запроса требуется определить, является ли данная раскладка промежуточной при перекладывании со стержня \(s\) на \(t\) при оптимальном перекладывании. Раскладка является промежуточной, если она встречается при оптимальном перекладывании со стержня \(s\) на стержень \(t\).