Longest Increasing Path in a Matrix

Given an $n \times m$ matrix filled with integers, your task is to determine the length of the longest increasing path in the matrix.

An increasing path is defined as a sequence of cells $p_1, p_2, \ldots, p_k$ such that for every $1 \leq i < k$, the following conditions hold:

• The value in cell $p_{i+1}$ is strictly greater than the value in $p_i$.
• $p_{i+1}$ is adjacent to $p_i$ (adjacency is defined only horizontally or vertically).

Please read the input from stdin and output the result to stdout as described in the input/output sections.

inputFormat

The input begins with two integers n and m representing the number of rows and columns of the matrix, respectively.

This is followed by n lines, each containing m integers separated by spaces, representing the matrix.

Example:

3 3
9 9 4
6 6 8
2 1 1

outputFormat

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

Example:

4

## sample

3 3
9 9 4
6 6 8
2 1 1

4