Fusion

The first cold fusion reactor was finished today and cleared for operation. When it was started for the first time, nothing happened.

The physicists checked their calculations over and over, and then three engineers found the cause. Two atoms inside the reactor have become α-stuck.

The reactor can be seen as a grid with $R$ rows and $C$ columns. Each cell is empty, holds one deuterium atom (two of those atoms are the α-stuck ones), or is blocked off by a control rod that prevents a runaway reaction. Each cell is adjacent to the four cells above it, below it, to its left and to its right, and a cell on the border of the reactor has fewer than four neighbors.

You can give the reactor a fusion instruction by naming two atoms to be fused. The two atoms fuse only if they sit in adjacent cells, or if a path of adjacent empty cells runs from one of them to the other. When two atoms fuse they produce helium that floats away, and both cells they occupied become empty.

To repair the reactor you have to fuse the two α-stuck atoms with each other. What is the fewest number of instructions the reactor needs for that?

Figure 1: the reactor of the first example input. Black cells are blocked off by control rods, blue circles are deuterium atoms, and the yellow circles are the two α-stuck atoms. One optimal sequence of fusions is shown as well.

Will you and your fellow engineers clear the last barrier to cold fusion?

The first line contains two integers $R$ and $C$, the number of rows and the number of columns of the reactor ($1 \le R \le 1000$, $1 \le C \le 1000$).

Each of the next $R$ lines describes one row of the reactor and holds exactly $C$ characters.

• . is an empty cell.
• # is a cell blocked off by a control rod.
• O is a cell holding a deuterium atom.
• A is a cell holding an α-stuck atom.

The input holds exactly two A characters.

Print the fewest fusion instructions needed to fuse the two α-stuck atoms with each other. If they cannot be fused, print -1 instead.