Longest Increasing Path in a Matrix

You are given a matrix of size m × n. Your task is to determine the length of the longest strictly increasing path in the matrix. You may move in one of the four cardinal directions (up, down, left, right) at each step, and you cannot move diagonally or visit the same cell more than once in a single path.

More formally, let the matrix be denoted as \(A\) where \(A_{i,j}\) is the element in the \(i^{th}\) row and \(j^{th}\) column. You need to find the maximum length of a sequence \(A_{i_1,j_1}, A_{i_2,j_2}, \ldots, A_{i_k,j_k}\) such that for each \(1 \leq t < k\):

\(A_{i_{t+1},j_{t+1}} > A_{i_t,j_t}\)

The path can start from any cell.

inputFormat

The first line of input contains two integers m and n — the number of rows and columns of the matrix, respectively.

Each of the next m lines contains n space-separated integers representing the rows of the matrix.

outputFormat

Output a single integer, which is the length of the longest increasing path in the matrix.

3 3
9 9 4
6 6 8
2 1 1

4