Longest Increasing Path in a Matrix

Given a matrix of integers with dimensions ( M \times N ), where each cell represents an elevation, find the length of the longest strictly increasing path from any cell. From each cell, you can move to one of the four adjacent cells (up, down, left, right) if the adjacent cell has a higher value than the current cell. This problem requires you to output the maximum length of any increasing path in the grid.

Note: The path must be strictly increasing, i.e., if you are at cell ( (i,j) ) with value ( v ), you can only move to a neighbor with a value greater than ( v ).

inputFormat

The first line contains two integers ( M ) and ( N ) separated by a space, representing the number of rows and columns of the matrix. Each of the next ( M ) lines contains ( N ) space-separated integers representing the matrix values.

outputFormat

Output a single integer representing the length of the longest strictly increasing path in the matrix.## sample

3 3
9 9 4
6 6 8
2 1 1

4