Perfect Circular Grid

A perfect circular grid is defined as a grid in which, for every cell, if you follow the arrow in that cell repeatedly, you will eventually return to the starting cell. The grid is given as R rows and C columns. Each cell contains an arrow that points to one of its adjacent neighbors. The only allowed arrow directions are:

• U: Up — moves from cell (r, c) to (r-1, c) (if r > 0)
• D: Down — moves from cell (r, c) to (r+1, c) (if r < R-1)
• L: Left — moves from cell (r, c) to (r, c-1) (if c > 0)
• R: Right — moves from cell (r, c) to (r, c+1) (if c < C-1)

Formally, if we denote the function defined by the arrows as \(f\), a grid is perfect if for every cell \(i\) we have \[ \exists\, k \ge 1 \text{ such that } f^k(i)=i. \]

You are allowed to modify the arrow in any cell. Modifying a cell means choosing a different allowed arrow (with cost 1 modification). Your task is to compute the minimum number of modifications needed so that the grid becomes perfect (i.e. every cell lies on a cycle that includes itself).

Hint: In the initial grid each cell defines a function \(f: S \to S\) where \(S\) is the set of cells. The grid is perfect if and only if \(f\) is a permutation (a bijection), i.e. every cell has exactly one incoming arrow as well as one outgoing arrow. Thus the problem reduces to changing as few cells as possible so that the resulting function is a permutation and, for every cell \(i\), the arrow chosen is one of its allowed moves.

inputFormat

The first line contains two integers R and C (the number of rows and columns respectively).

Then follow R lines, each line containing a string of length C consisting only of the characters U, D, L, and R. It is guaranteed that every arrow points to a valid neighboring cell (i.e. no arrow points outside the grid).

outputFormat

Output a single integer—the minimum number of modifications required to make the grid perfect.

sample

2 2
RD
UL

0