Blenjeel Sand Worms and Color Wriggles

Time Limit: 2 Seconds Memory Limit: 65536 KB

The Blenjeel sand worms slither across the sandy surface of the planet Blenjeel. As the planet’s only known inhabits, they protect their homeland by attacking and devouring from underneath anyone who steps foot on their planet.

Of course, the sand worms need to be strong, flexible, and able to slither as quietly as possible. All teenage sand worms are conscripted to a six-month boot camp, where they endure intense training. The most demanding of the training exercise is the famous "wriggle test", which requires worm cadets to slither from one position to a parallel position several hundreds of feet away. Only the toughest, most determined of worms survive.

The exercise is so famous that the Jedi Academy’s CS101 has its students solve a puzzle based on Blenjeel Boot Camp. And that puzzle goes something like this:

Given an n × m board (3 ≤ n ≤ 6, 5 ≤ m ≤ 50) wriggle a Blenjeel sand worm (of length n) from the left column to the right column, ensuring the worm never simultaneously occupies two squares of the same color.

Consider the following 3 × 5 board, where each number represents a different color, and the worm is represented by the chain of circles:

One of two possible moves is to pull the bottom of the worm to the right so it’s positioned as follows:

Now we can pull from the other end of the worm to carry it through three different positions:

Through a series of additional moves, it’s possible to wriggle the worm into the target position where the body of the worm is completely in the rightmost column:

It’s acceptable for the worm to reach the right column in either orientation.

Your job is to write a program that reads in a series of boards as described above, and for each prints out the minimum number of wriggles needed to move the worm from the left column to the right (or -1 if there’s no solution).

Input

The data will be n rows of m items. In each row will be digits representing a color (colors are represented by the digits 1 through 7 – not all boards will use all 7 colors). The colors in the leftmost column of each input board are guaranteed to be unique. Each board is separated from the next by a blank line. The end of input will be signaled by a standalone 'end'. There will be a blank line between the last board and 'end'.

Output

For each board read, print the minimal number of wriggles needed to move the worm from the left column to the right (or -1 if there's no solution) followed by a newline.

Sample Input

12324 
31312 
41431 
 
234234 
342112 
421311 
 
234233 
342112 
421331 
 
41344411122134441231 
22313433414323312312 
12231221312124143323 
 
41251355234115 
13515533543252 
34212412323543 
52454355242421 

364311121136362 
151446122112155 
434232633624623 
561614315456464 
234426516251346 

end

Sample Output

Submit