Turn On the Light

Sunyoung is designing a rectangular electronic circuit with height N and width M. The circuit consists of N × M square tiles, and every tile is parallel to the sides of the rectangle. Each tile has one wire connecting two opposite corners.

The power source is connected to the upper-left corner of the circuit, and the light bulb is connected to the lower-right corner. The bulb turns on only when there is a path along wires from the power source to the bulb. To turn on the bulb, Sunyoung may rotate any number of tiles by 90 degrees.

In the picture above, the bulb is off. If any tile in the second column from the right is rotated by 90 degrees, the power source and the bulb become connected, and the bulb turns on. Find the minimum number of tiles that must be rotated to turn on the bulb.

The first line contains two integers N and M. Each of the next N lines describes the current state of the circuit. Each line has length M, and each character is either / or \.

1 ≤ N, M ≤ 500

If the bulb can be turned on, print the minimum number of tiles that must be rotated. If it is impossible, print NO SOLUTION.