D :: Bacteria

Time Limit: 1 Second    Memory Limit: 32768 KB

In order to simplify the study of bacteria, their configuration space is sometimes downsized by modeling the microscopic pictures as a simple two-dimensional grid. As you can see a grid-simplification of a picture of a famous bacterium known as Dilbacterium, some cells of the grid are occupied by the body of bacteria, while the other cells remain empty.
Some empty cells of the grid are already occupied with other dead material. Such grid cells cannot be occupied by the bacteria. Let’s G be the set of all cells of the grid that are not filled with dead material.
Two cells of a grid are called adjacent if they share a common edge. A sequence L of grid cells is called a path if every two consecutive cells of ? are adjacent. A set S of grid cells is called connected if for all c1, c2 € S there is a path including c1 and c2 that only uses the members of S. Now, a grid-simplified bacterium (GSB) can be formally defined as a fixed-size connected subset of G.
As real living bacteria move, their movement should also be defined in the grid-simplified model. The movement of bacteria in this model has again a discrete definition. A single move of a GSB with the set of grid cells S, is defined as removing a grid cell c1 € S and adding a grid cell c2 € G - S such that the sets S-{c1}, S U {c2} and (S - {c1}) U {c2} are connected. Now, the set (S - {c1}) U {c2} is the new valid configuration of the GSB after this single movement. By configuration, we mean the position of a GSB together with its shape.
A GSB can perform a series of movements in order to achieve a totally different configuration. Clearly, there are many different series of movements for a GSB with a single initial configuration, that all lead to the same final configuration. Given an initial and a target configuration of a GSB, your job is to find the minimum number of movements needed to lead its initial configuration to the target configuration. You can assume that the initial and the target configurations have no grid cells in common.

Input

There are multiple test cases in the input. Each test case starts with a line containing space-separated integers m and n (1 <= m, n <= 200), which denote the height and width of the grid respectively. There are n characters in each of the next m lines which describe the structure of the m × n grid, and the initial and target configuration of the GSB. The characters of the grid can be one of the following:

  • '.' representing empty cells
  • '#' representing grid cells occupied with dead material
  • 'x' representing grid cells of the initial configuration
  • 'o' representing grid cells of the target configuration

It is guaranteed that the number of grid cells occupied in the initial and target configurations are equal and less than 10.

The input terminates with a line of the form "0 0" which should not be processed as a test case.

 

Output

Write the result of the ith test case on the ith line of output.
For each test case, write the minimum number moves needed to lead the GSB from its initial configuration to the target configuration. If there is no way to reach the target configuration, write "No solution" (without quotation marks).

Sample Input

2 3
...
x#o
2 3
x.o
x#o
2 3
#..
x#o
9 9
.xxx.....
.xxx...#.
########.
.......#.
.#####.#.
.#.oo#.#.
.#oooo.#.
.#######.
.........
0 0

Sample Output

4
3
No solution
41
Submit

Source: Tehran, Asia Region - Regional 2011