Minimize Longest Common Prefix of Two Paths

Given an $n\times m$ matrix containing lowercase letters, where each cell $(i,j)$ holds a letter, you are to choose two valid paths from the top-left cell $(1,1)$ to the bottom-right cell $(n,m)$. A path is valid if you can only move either down or right at each step. The string corresponding to a path is formed by concatenating the letters along the path in order.

Your task is to select two valid paths such that the length of the longest common prefix (LCP) of their corresponding strings is minimized. Here, the LCP of two strings is the longest initial segment that is identical in both strings.

Note:

• If $n=1$ or $m=1$, there is only one valid path, and hence the only possibility is to use that path twice, yielding an LCP equal to the entire path length, i.e. $n+m-1$.
• For $n,m\ge 2$, one typical strategy is to choose one path that takes the right move from $(1,1)$ and the other that takes the down move. In this case, the second characters of the two path strings are $a_{1,2}$ and $a_{2,1}$ respectively. Thus, if $a_{1,2}\neq a_{2,1}$ the longest common prefix is just the first character; otherwise it is at least $2$.

inputFormat

The first line contains two integers $n$ and $m$ ($1\le n,m\le 10^5$), with the additional constraint that $n\times m\le 10^5$, representing the number of rows and columns, respectively.

Each of the next $n$ lines contains a string of $m$ lowercase letters, representing the grid.

outputFormat

Output a single integer --- the minimum possible length of the longest common prefix of the two selected path strings.

sample

1 3
abc

3