말 타기

체스가 스포츠라는 사실은 잘 알려져 있다. 하지만 승마를 즐기는 Dima는 체스를 지루하게 여기며 전혀 스포츠라고 생각하지 않는다. 그의 친구 Sasha는 체스가 얼마나 복잡하고 흥미로울 수 있는지 보여 주기로 했다.

Sasha는 $8 \times 8$ 체스판에 나이트 $k$마리를 놓았다. 나이트들은 산책로에 있고 마구간으로 돌아가려 하지만, 집으로 가는 길을 기억하지 못한다.

다음 조건을 만족하면 나이트들이 마구간에 있는 것이다. 아래쪽 $k \text{ div } 8$개 행이 나이트로 가득 차 있고, 그다음 행에는 가장 왼쪽 칸에만 나이트가 있다. $k \bmod 8 \ne 0$이면 그 행에는 나이트 $k \bmod 8$마리가 가장 왼쪽 자리를 차지한다.

$k=11$일 때 목표 칸을 나타낸 그림이다. 나이트 한 마리당 칸 하나가 목표다.

나이트는 체스 규칙대로 움직인다. 즉 한 방향으로 정확히 두 칸 이동한 뒤 다른 방향으로 정확히 한 칸 이동한다.

나이트의 가능한 이동

나이트는 한 번에 한 마리씩, 어떤 순서로든 움직인다. 같은 순간에 한 칸에는 나이트가 최대 한 마리만 있을 수 있다. Dima는 이 문제를 이틀 동안 붙잡고 있었다. 두 나이트가 같은 칸을 차지하는 일이 없으면서 모든 나이트가 마구간에 도착하도록 이동 순서를 찾아라. 이동 횟수를 최소화할 필요는 없지만, 전체 이동 횟수는 1500번을 넘으면 안 된다.

첫 줄에 정수 $k$(판 위의 나이트 수, $1 \leq k \leq 64$)가 주어진다. 다음 $k$개 줄에는 나이트의 위치가 한 줄에 하나씩 xy 형식으로 주어진다. x는 열을 나타내는 문자이고 y는 행을 나타내는 숫자다. 열은 왼쪽의 a부터 오른쪽의 h까지, 행은 아래의 1부터 위의 8까지 번호가 매겨진다.

첫 줄에 이동 횟수를 출력한다. 이어서 이동을 한 줄에 하나씩 순서대로 xy-zt 형식으로 출력한다. x와 z는 열을 나타내는 문자이고 y와 t는 행을 나타내는 숫자다. 이동 횟수를 최소화할 필요는 없지만 전체 횟수는 1500번을 넘으면 안 된다.