Minimizing Reversible Words in an Archaeological Grid

An archaeological team has discovered a mysterious white wall covered with an unknown language. The wall is divided into a grid of \(n\) rows and \(m\) columns. Some grid cells contain a capital letter (from A to Z), while others are blank.

A contiguous sequence (in a row or a column) of letters (reading horizontally or vertically) forms a word. However, the reading order is not fixed. For each row the letters may be read from left to right or from right to left; similarly, for each column the letters may be read from top to bottom or from bottom to top. In other words, each row (or column) when read in the decided order will produce a sequence of words (adjacent words are separated by one or more blank cells).

Unfortunately, the exact reading orders (direction for each row and column) are unknown. However, it is observed that for every row (or column) the obtained words all satisfy one of the following conditions:

1. Each word is lexicographically not less than its reversed string, i.e. \(w \geq \mathrm{rev}(w)\).
2. Each word is lexicographically not greater than its reversed string, i.e. \(w \leq \mathrm{rev}(w)\).

That is, for each row or column, you must choose one reading order so that every contiguous sequence of letters has the property of being either at least as large as its reverse (in lexicographical order) or at most as large.

After the reading orders are determined for all rows and columns, a dictionary for this unknown language is constructed from the words that appear. A word is said to be "reversible" if its reversed string is also a word in the dictionary. Note that if a word, when reversed, results in a different word, then both are counted separately; however, a palindrome (a word that reads the same backwards) is only counted once.

Your task is to choose a valid reading order for each row and column (that is, one of the two directions per row/column, subject to the condition above) such that the number of reversible words in the resulting dictionary is minimized. Output this minimum number.

Note: For a given contiguous segment of letters, if its natural order is denoted by \(s\) and its reverse by \(r\), then:

• If \(s > r\) then the only possibility to satisfy \(w \geq \mathrm{rev}(w)\) is to read it in the natural order (yielding \(s\)).
• If \(s < r\) then the only possibility to satisfy \(w \leq \mathrm{rev}(w)\) is to read it in the reversed order (yielding \(r\)).
• If \(s = r\) (i.e. the segment is a palindrome), then both orders work.

Each row or column that contains at least one non-palindromic contiguous segment forces its reading direction. If a row/column has only palindromic segments, you may choose the reading order arbitrarily.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \leq n, m \leq 1000\)), representing the number of rows and columns of the grid.

The following \(n\) lines each contain a string of length \(m\). Each character is either a capital letter ('A'–'Z') or a dot \('.'\) representing a blank cell.

outputFormat

Output a single integer --- the minimum number of reversible words in the dictionary. A word is considered reversible if its reversed string also appears in the dictionary. If a word and its reverse are different, count them separately; if the word is a palindrome, count it only once.

sample

2 5
BOY.A
YOB.A

3