Background

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.

Problem Description

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.

Input Format

The first line contains two numbers $n,m$.

The next $n$ lines each contain $m$ characters, describing the whole matrix.

Output Format

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

3 3
abe
bcx
exy

2

Hint

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