블렌질 모래 벌레와 색깔 꿈틀 이동

모래 벌레들은 블렌질 행성의 모래 표면을 기어 다닌다. 이 행성에 알려진 유일한 거주자인 이들은, 행성에 발을 들인 상대를 땅속에서 습격해 집어삼키며 고향을 지킨다.

모래 벌레는 강하고 유연해야 하며, 최대한 조용히 기어 다닐 수 있어야 한다. 청소년기의 모래 벌레는 모두 6개월간의 혹독한 신병 훈련소로 보내진다. 그중 가장 힘든 과정이 바로 유명한 꿈틀 시험으로, 훈련생은 수백 피트 떨어진 평행한 위치까지 기어가야 한다. 가장 강인한 벌레만이 살아남는다.

이 시험에서 다음 퍼즐이 유래했다.

$n \times m$ 크기의 판이 주어진다($3 \le n \le 6$, $5 \le m \le 50$). 각 칸에는 색이 $1$부터 $7$까지의 숫자로 적혀 있다(한 판이 일곱 색을 모두 쓸 필요는 없다). 길이 $n$의 모래 벌레는 $n$개의 칸이 이어진 사슬로, 이웃한 칸끼리는 상하좌우로 맞닿아 있다. 벌레는 처음에 맨 왼쪽 열 전체를 차지하고 있으며, 맨 오른쪽 열 전체를 차지하는 상태에 도달해야 한다(세로 방향은 위아래 어느 쪽이든 괜찮다).

벌레는 언제나 색이 모두 서로 다른 $n$개의 칸을 차지해야 한다. 즉, 같은 색의 두 칸을 동시에 덮을 수 없다. (맨 왼쪽 열의 색은 항상 서로 다르다고 보장되므로, 시작 상태는 언제나 올바르다.)

한 번의 꿈틀은 다음과 같다. 벌레의 두 끝 중 하나를 골라 그 끝을 상하좌우로 맞닿은 칸으로 옮긴다. 나머지 각 마디는 옮기는 끝 쪽 이웃이 방금 있던 칸으로 밀려 들어가고, 반대쪽 끝이 있던 칸은 비게 된다. 예를 들어 시작 열에서 아래쪽 끝을 오른쪽으로 한 칸 당길 수 있다.

이어서 반대쪽 끝을 당겨 벌레를 또 다른 위치들로 옮길 수 있다.

옮기는 끝의 목적지 칸은 판 안에 있어야 하고, 밀림이 끝난 뒤에도 남아 있는 마디가 차지하지 않은 칸이어야 한다(다만 반대쪽 끝이 비우는 바로 그 칸이라면 괜찮다). 이동한 뒤에도 벌레가 차지한 $n$개의 칸은 모두 색이 서로 달라야 한다.

여러 번 꿈틀거리면 벌레를 맨 오른쪽 열 전체로 옮길 수 있는 경우가 있다.

벌레를 맨 왼쪽 열에서 맨 오른쪽 열로 옮기는 데 필요한 최소 꿈틀 횟수를 출력하라. 불가능하면 $-1$을 출력한다.

입력에는 하나 이상의 판이 들어 있다. 각 판은 정확히 $m$개의 문자로 이루어진 $n$개의 줄이며, 각 문자는 그 칸의 색을 나타내는 $1$부터 $7$까지의 숫자다. 모든 판에서 맨 왼쪽 열의 색은 서로 다르다고 보장된다. 이웃한 두 판은 빈 줄 하나로 구분된다. end만 적힌 줄이 입력의 끝을 나타내며, 마지막 판과 이 end 줄 사이에도 빈 줄이 하나 있다. $n$과 $m$은 각 판의 모양으로 정해진다($3 \le n \le 6$, $5 \le m \le 50$).

각 판에 대해 주어진 순서대로, 벌레를 맨 왼쪽 열에서 맨 오른쪽 열로 옮기는 데 필요한 최소 꿈틀 횟수를 한 줄에 하나씩 출력하라. 방법이 없으면 $-1$을 출력한다.