Help Monks

아주 먼 왕국에 유명한 Lio Shan 수도원이 있다. 오래전 신들은 수도원의 잔디밭에 다이아몬드 기둥 세 개를 세웠다. 또한 신들은 한 기둥에 지름이 서로 다른 황금 원반 n개를 놓았다(아래에서 위로 갈수록 지름이 작아지는 순서였다). 그리고 다음 규칙에 따라 모든 원반을 첫 번째 기둥에서 세 번째 기둥으로 옮기라고 명령했다.

• 한 번의 이동에는 원반 하나만 옮길 수 있다.
• 더 큰 원반을 더 작은 원반 위에 놓을 수 없다.

신들의 뜻이 이루어진 뒤 무슨 일이 일어날지를 두고 모두가 동의하는 견해는 없었다. 어떤 사람들은 모두에게 세계 평화와 영원한 행복이 찾아올 것이라고 장담했지만, 다른 사람들은 왕국에 공산… (이런, 내가 무슨 쓸데없는 말을 하는 거지?) 아마겟돈이 닥칠 것이라고 예언했다. 하지만 모두가 이 문제를 2n - 1번보다 적은 이동으로 해결하는 것은 불가능하다는 사실을 알았고, 게으른 Lio Shan 수도사들은 문제를 풀기 시작조차 하지 않았으므로, 문제는 끝내 해결되지 않았지만 모두가 평화롭게 살며 아무도 아마겟돈을 두려워하지 않는다.

하지만 최근 수도원의 형편이 좋지 않았고, 현명한 수도원장 Ku Sean Sun은 일부 원반의 가장자리를 잘라 그 금을 더 유익한 일에 써야 했다. 수도원장에게 냉방 시설을 누릴 자격이 있다고 생각하지 않는가? 게다가 일 년 내내 수도원에 머무는 것은 너어어무 지루하다… 가끔은 새로운 일도 해 봐야 한다. 예를 들면 스키를 타러 가는 것처럼… Ku Sean Sun은 시간이 좀 지나고 나서야 자신이 얼마나 큰 실수를 저질렀는지 깨달았다. 가장자리를 자르고 나니 일부 원반의 지름이 같아졌고, 이는 이전에는 불가능했던 몇몇 이동이 마침내 가능해졌다는 뜻이었다(신들은 같은 지름의 원반 위에 원반을 놓는 것을 금지한 적이 없지 않은가). 따라서 일어날 수도 있는 아마겟돈은 신들이 처음 계획했던 것보다 더 일찍 찾아올 수 있다. 훨씬 더 일찍 말이다. 너무나 일찍 찾아오는 바람에 Ku Sean Sun은 원하는 만큼 스키를 타거나 냉방기 아래에서 쉴 시간조차 없을 것이다.

현명한 수도원장은 그런 마지막 상황만큼은 절대 일어나게 둘 수 없었기에, 아주 늙고 지혜로운 마녀 PikiWedia에게 도움을 청했다. 어쩌면 그녀라면 신들의 문제를 푸는 데 필요한 최소 이동 횟수를 알아낼 수 있을지도 모른다. 하지만 마녀는 카드를 펼쳐 보았으나 수도원장에게 줄 답을 찾지 못했다. 그러자 그는 당신에게 도움을 청했다.

원반의 개수와 지름이 주어졌을 때 이 문제의 최단 해법을 찾을 수 있는가? 지름이 같은 원반끼리는 서로 위에 놓을 수 있지만, 마지막에 세 번째 기둥에 놓인 원반의 순서는 처음에 첫 번째 기둥에 놓였던 원반의 순서와 일치해야 한다는 점에 유의한다.

첫째 줄에 원반의 개수인 정수 n (1 ≤ n ≤ 20)이 주어진다. 둘째 줄에는 Ku Sean Sun이 원반의 가장자리를 자른 뒤의 지름을 나타내는 n개의 정수 di이 주어진다. 지름은 아래에서 위로의 순서로 주어진다 (1 ≤ di ≤ 20, besides, di ≥ di + 1 for any 1 ≤ i < n).

첫째 줄에 신들의 문제를 해결하기 위한 최소 이동 횟수 m을 출력한다. 이어지는 m개 줄에는 이동에 대한 설명으로, 원반을 옮겨 오는 기둥의 번호와 원반을 옮겨 놓는 기둥의 번호를 각각 나타내는 공백으로 구분된 두 양의 정수 si와 ti를 출력한다 (1 ≤ si, ti ≤ 3, si ≠ ti).

세 번째 테스트는 원반의 반지름이 같더라도 마지막에 원반의 순서가 동일하게 유지되어야 함을 보여 준다는 점에 유의한다. 이 조건을 만족할 필요가 없었다면 신들의 과제는 더 적은 이동 횟수로 해결할 수 있었을 것이다(세 번, 즉 원반 세 개를 첫 번째 기둥에서 세 번째 기둥으로 옮기기만 하면 된다).