P10270 Curious Baby.

> Roads are made by people’s own hands. > > Wine and bread are gained through work. > > Tiny new sprouts stretch out their leaves, > > Fighting off sleepiness among piles of potions. > > A bit more, just a bit more time, > > To read the next page of the book.

You are given an $n \times m$ matrix, where each position $(i,j)$ is a lowercase letter. Define the string of a path as the string formed by concatenating the characters on the path in order. Please find two paths from $(1,1)$ to $(n,m)$, where you may only move down or right, to minimize the length of the longest common prefix of the two path strings.

The first line contains two numbers $n,m$. The next $n$ lines each contain $m$ characters, describing the whole matrix.

Output one number, which is the minimum possible length of the longest common prefix.

### Explanation of Sample 1 The two chosen paths are: - $(1,1)\rightarrow (1,2)\rightarrow (1,3)\rightarrow (2,3)\rightarrow (3,3):$ `abexy`. - $(1,1)\rightarrow (1,2)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3):$ `abcxy`. Their longest common prefix has length $2$. It can be proven that there is no better solution. ### Constraints and Notes For $30\%$ of the testdata, $1 \le n,m \le 5$. For $50\%$ of the testdata, $1 \le n,m \le 50$. For the other $20\%$ of the testdata, the matrix is randomly generated and contains only letters `a,b`. For $100\%$ of the testdata, $1 \le n,m \le 2\times 10^3$, and the input contains only integers and lowercase letters. Translated by ChatGPT 5