Shortest Palindromic Path in a Grid

Given an \( n \times m \) grid filled with lowercase letters, find the length of the shortest path from the top-left cell to the bottom-right cell such that the string formed by concatenating the characters along the path is a palindrome. In each move, you are only allowed to move either right or down.

If no palindromic path exists, output \( -1 \). A string \( s \) is considered palindromic if it satisfies \( s = s^R \), where \( s^R \) is the reverse of \( s \).

inputFormat

The input is given via standard input (stdin). The first line contains two integers \( n \) and \( m \), representing the number of rows and columns respectively. This is followed by \( n \) lines, each containing a string of length \( m \), which represents a row of the grid.

outputFormat

Output a single integer to standard output (stdout): the length of the shortest palindromic path from the top-left to the bottom-right cell of the grid, or \( -1 \) if such a path does not exist.

3 3
aab
bcb
baa

5