Casper's Circuit

Casper is designing an electronic circuit on a \(N \times M\) rectangular grid plate. There are \(N \times M\) square tiles that are aligned with the grid. Each tile has a wire connecting two opposite corners. In other words, each tile contains either a '\\' diagonal (connecting the top left and bottom right corners) or a '/' diagonal (connecting the top right and bottom left corners).

A power source is connected to the top left corner of the plate and a lamp is connected to the bottom right corner. The lamp will be turned on only if there is a continuous path of connected wires from the power source to the lamp. In order to achieve this, any number of tiles can be rotated by \(90^\circ\) (either clockwise or counterclockwise), which effectively toggles the tile from '\\' to '/' or vice versa.

The task is to determine the minimal number of rotations required so that there is a connected path from the power source to the lamp. If it is impossible to complete the circuit, output \(-1\).

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of rows and columns of tiles). Each of the following \(N\) lines contains a string of length \(M\). Each character in the string is either '\\' or '/', representing the default orientation of the tile.

outputFormat

Output a single integer representing the minimum number of \(90^\circ\) rotations required to create a continuous path from the top left corner to the bottom right corner of the plate. If there is no solution, output \(-1\).

sample

1 1
\

0