Blenjeel Sand Worms and Color Wriggles

Sand worms slither across the sandy surface of the planet Blenjeel. As the planet's only known inhabitants, they defend their homeland by attacking and devouring, from underneath, anyone who sets foot on their world.

A sand worm must be strong, flexible, and able to slither as quietly as possible. Every teenage sand worm is sent to a six-month boot camp of intense training. The hardest exercise is the famous wriggle test: a cadet must slither from one position to a parallel position hundreds of feet away. Only the toughest worms survive.

That test inspired the following puzzle.

You are given an $n \times m$ board ($3 \le n \le 6$, $5 \le m \le 50$). Every cell has a color written as a digit from $1$ to $7$ (a board need not use all seven colors). A sand worm of length $n$ is a chain of $n$ cells in which consecutive cells are orthogonally adjacent (up, down, left, or right). The worm starts by occupying the entire leftmost column and must reach a state where it occupies the entire rightmost column (either vertical orientation is acceptable).

At every moment the worm must occupy $n$ cells whose colors are all distinct; it may never simultaneously cover two cells of the same color. (The colors of the leftmost column are guaranteed distinct, so the starting position is always valid.)

A single wriggle works as follows: choose either end of the worm and move that end to an orthogonally adjacent cell. Every other segment then shifts into the cell that its neighbor toward the moving end just occupied, and the opposite end's cell is vacated. For example, from the starting column you may pull the bottom end one step to the right:

You may then pull from the other end to carry the worm through further positions:

The destination of the moving end must lie on the board and must not be occupied by any segment that remains after the shift (it may, however, be the very cell that the opposite end is vacating). After the move, all $n$ occupied cells must still have distinct colors.

Through a series of wriggles it is sometimes possible to bring the worm entirely into the rightmost column:

Print the minimum number of wriggles needed to move the worm from the leftmost column to the rightmost column, or $-1$ if it is impossible.

The input contains one or more boards. Each board is $n$ lines of exactly $m$ characters, where every character is a digit from $1$ to $7$ giving that cell's color. The colors in the leftmost column of every board are guaranteed to be distinct. Consecutive boards are separated by a single blank line. A line containing only end marks the end of the input, and there is a blank line between the last board and that end line. Both $n$ and $m$ are determined by the shape of each board ($3 \le n \le 6$, $5 \le m \le 50$).

For each board, in the order given, print on its own line the minimum number of wriggles needed to move the worm from the leftmost column to the rightmost column, or $-1$ if there is no solution.