Longest Increasing Path in a Matrix

You are given a matrix of integers with dimensions \(n \times m\). Your task is to find the length of the longest strictly increasing path in the matrix. From any cell, you can move in one of the four directions: up, down, left, or right. A path is considered strictly increasing if every consecutive number in the path is greater than the previous one.

Note: The length of a path is defined as the number of cells in it. For example, if the matrix is

9 9 4
6 6 8
2 1 1

one of the longest increasing paths is 1 → 2 → 6 → 9, so the answer is 4.

The problem may require careful exploration such as Depth-First Search (DFS) combined with memoization or dynamic programming techniques.

inputFormat

The first line contains two integers \(n\) and \(m\), denoting the number of rows and columns of the matrix, respectively.

This is followed by \(n\) lines, each containing \(m\) space-separated integers representing the matrix.

outputFormat

Output a single integer — the length of the longest strictly increasing path in the matrix.

## sample

3 3
9 9 4
6 6 8
2 1 1

4

</p>