많은 하노이 탑

원래의 하노이 탑 게임에는 기둥 세 개와 원판들이 있다. 처음에는 모든 원판이 한 기둥에 쌓여 있고, 위에서 아래로 갈수록 반지름이 커진다. 다음 그림은 원래 게임의 시작 상태이다.

원판에는 1번부터 n번까지 번호가 붙어 있고, n은 원판의 개수이다. 1번이 가장 작은 원판이고 n번이 가장 큰 원판이다. 그림에서 기둥은 A, B, C로 표시되어 있다. 목표는 여러 번의 이동을 거쳐 모든 원판을 다른 기둥으로 옮기는 것이다. 한 번의 이동에서는 임의의 기둥 맨 위의 원판을 다른 기둥 맨 위에 올릴 수 있는데, 올리는 원판은 그 아래 원판보다 작아야 한다. 빈 기둥으로 맨 위의 원판을 옮길 수도 있다. 이동은 출발 기둥과 도착 기둥만 적으면 된다. 예를 들어 위 그림에서 A에서 B로, A에서 C로, B에서 C로 옮기면 기둥 A에는 3, 4, 5번 원판이 남고 기둥 C에는 1번과 2번 원판이 놓인다.

제조사는 3개 대신 k개의 기둥이 있는 세트를 만들었다. 기둥은 A, B, C 대신 1번부터 k번까지 번호로 구분한다. 세트에는 n = k(k-1)/2개의 원판이 들어 있다. 상자에는 이 퍼즐을 $2(k-1)^2$번 이하의 이동으로 풀 수 있다고 적혀 있다. 이 주장이 맞음을 보이는 프로그램을 작성하라.

기둥의 수 k, 모든 원판의 출발 기둥 s, 도착 기둥 e가 주어졌을 때, 퍼즐을 푸는 이동을 $2(k-1)^2$번 이하로 만들어라.

첫 번째이자 유일한 입력 줄에 정수 세 개 k ($3 \le k \le 1000$), s ($1 \le s \le k$), e ($1 \le e \le k$, $e \ne s$)가 주어진다. k는 기둥의 개수이고, s는 $k(k-1)/2$개의 원판이 시작하는 기둥 번호이며, e는 같은 원판들이 도착해야 하는 기둥 번호이다.

첫 줄에는 이동 횟수 m을 나타내는 양의 정수 하나를 출력한다. 이어서 m줄에 걸쳐 각 이동의 출발 기둥 a와 도착 기둥 b를 공백으로 구분하여 출력한다 ($a \ne b$). 이동은 실제로 수행되는 순서대로 적는다.

• 대부분의 퍼즐에는 여러 가지 해법이 있다. 올바른 해법이면 어떤 것이든 인정된다.
• 최적해를 낼 필요는 없다. 올바르고 이동 횟수가 $2(k-1)^2$번 이하이면 인정된다.