방향판

방향판은 화살표로 채워진 행렬이다. 화살표 하나가 칸 하나를 모두 차지하며, 왼쪽, 오른쪽, 위, 아래 중 한 방향을 가리킨다.

칸의 위치는 (행, 열)로 나타내고, 가장 왼쪽 위 칸은 (0, 0)이다.

칸 (r, c)에서 다음에 이동할 칸은 그 칸에 적힌 화살표가 정한다. 왼쪽이면 (r, c-1), 오른쪽이면 (r, c+1), 위쪽이면 (r-1, c), 아래쪽이면 (r+1, c)로 이동한다.

방향판의 모든 행과 열은 순환한다. 그래서 방향판 바깥으로 나가면 반대쪽에서 다시 들어온다. 예를 들어 방향판의 크기가 5 × 5인 경우에 (3, 0)에서 왼쪽으로 한 칸 이동하면 (3, 4)로 돌아오게 된다.

어느 칸에서 출발하든 화살표를 따라 계속 이동하면 언제나 출발한 칸으로 돌아오도록 방향판의 화살표를 바꾸려고 한다. 예를 들어 아래 그림과 같은 경우에 (1, 1), (1, 2), (2, 0), (2, 3)에 적힌 화살표를 바꿔서 항상 시작점으로 돌아오게 방향판을 바꿀 수 있다. 바꿔야 하는 화살표의 최소 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 방향판의 행의 개수 N과 열의 개수 M이 주어진다. (1 ≤ N, M ≤ 15)

둘째 줄부터 N개의 줄에 각각 길이 M인 문자열로 방향판의 정보가 주어진다. U는 위, D는 아래, L은 왼쪽, R은 오른쪽을 나타낸다.

주어진 방향판이 문제의 조건을 만족하도록 바꿔야 하는 화살표의 최소 개수를 출력한다.