Longest Increasing Path in a Matrix

Given an \( m \times n \) matrix of integers, your task is to find the length of the longest strictly increasing path in the matrix. From any cell, you can move in four directions: up, down, left, or right. You cannot move diagonally or leave the boundary of the matrix. The path may start at any cell, and a move is valid only if the next cell contains a value greater than the current one.

The problem can be mathematically expressed as follows: given a matrix \( A \), find the maximum length \( L \) such that there exists a sequence of indices \( (i_1, j_1), (i_2, j_2), \ldots, (i_L, j_L) \) which satisfies: \[ A_{i_1,j_1} < A_{i_2,j_2} < \cdots < A_{i_L,j_L} \] with each consecutive pair of indices being adjacent in one of the four primary directions.

Your solution should read input from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The first line of input contains two integers \( m \) and \( n \) representing the number of rows and columns respectively. The following \( m \) lines each contain \( n \) space-separated integers representing the matrix.

Example:

3 3
9 9 4
6 6 8
2 1 1

outputFormat

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

3 3
9 9 4
6 6 8
2 1 1

4