譯自 BalticOI 2011 Day1 T3「Switch the Lamp On」

有一種正方形的電路元件，在它的兩組相對(duì)頂點(diǎn)中，有一組會(huì)用導(dǎo)線連接起來，另一組則不會(huì)。

有 N×M 個(gè)這樣的元件，你想將其排列成 N 行 M 列放在電路板上。電路板的左上角連接電源，右下角連接燈泡。

試求：至少要旋轉(zhuǎn)多少個(gè)正方形元件才能讓電源與燈泡連通，若無解則輸出 NO SOLUTION。

Casper is designing an electronic circuit on a N×M rectangular grid plate. There are N×M square tiles that are aligned to the grid on the plate. Two (out of four) opposite corners of each tile are connected by a wire.

A power source is connected to the top left corner of the plate. A lamp is connected to the bottom right corner of the plate. The lamp is on only if there is a path of wires connecting power source to lamp. In order to switch the lamp on, any number of tiles can be turned by

90° (in both directions).

In the picture above the lamp is off. If any one of the tiles in the second column from the right is turned by 90° , power source and lamp get connected, and the lamp is on.

Write a program to find out the minimal number of tiles that have to be turned by 90° to switch the lamp on.

有多組測(cè)試數(shù)據(jù)。

第一行為測(cè)試數(shù)據(jù)組數(shù)，以下每組測(cè)試數(shù)據(jù)描述為：

第一行有兩個(gè)整數(shù) N 和 M。

在接下來的 N 行中，每行有 M 個(gè)字符。每個(gè)字符均為 "\" 或 "/"，表示正方形元件上導(dǎo)線的連接方向。

The first line of input contains two integer numbers N and M, the dimensions of the plate. In each of the following N lines there are M symbols – either  \ or / – which indicate the direction of the wire connecting the opposite vertices of the corresponding tile.

每組測(cè)試數(shù)據(jù)輸出描述：

輸出共一行，若有解則輸出一個(gè)整數(shù)，表示至少要旋轉(zhuǎn)多少個(gè)正方形元件才能讓電源與燈泡連通；若無解則輸出 NO SOLUTION。

There must be exactly one line of output. If it is possible to switch the lamp on, this line must contain only one integer number: the minimal number of tiles that have to be turned to switch on the lamp. If it is not possible, output the string: NO SOLUTION

1
3 5
\\/\\
\\///
/\\\\

1

對(duì)于 40% 的數(shù)據(jù)，1≤N≤4,1≤M≤5。

對(duì)于所有數(shù)據(jù)，1≤N,M≤500。