#2005 전선 잇기

13  5 s   128 MB  

Description

N×M 개의 정사각형 타일들로 이뤄진 전자회로가 주어진다. 타일은 두 개의 마주보는 꼭지점이 전선으로 이어져 있다.

아래의 그림과 같이 왼쪽 위 모서리에 전원이 연결 되어 있고, 전구는 오른쪽 아래 모서리에 연결되어있다. 전원에서 전구로 가는 전선의 연결이 존재할 때만 불이 켜진다. 초기 배치로는 전구에 불이 켜지지 않을 수 있으며, 타일들은 90도로 회전을 시킬 수 있다.

회전을 시키는 횟수를 최소화 하여 전구를 킬 수 있는 프로그램을 작성하라.

Input

입력의 첫 줄에 N과 M이 주어진다(1 ≤ N,M ≤ 500).

그 다음 줄부터 N행 M열로 타일들의 상태 ‘\’(왼쪽 위 모서리 에서 오른쪽 아래 모서리로 전선이 이어진 경우) 혹은 ‘/’ (반대의 경우)가 주어진다.

Output

전구를 키기 위한 최소 회전 수를 출력한다. 만약 불가능 할 경우에는 따옴표 없이 “NO SOLUTION”을 출력한다.

Sample Input

Sample Output

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