Longest Increasing Path in a Grid

You are given an \(N \times N\) matrix grid of positive integers. Your task is to find the length of the longest path from the top-left corner (i.e. cell (0, 0)) to the bottom-right corner (i.e. cell (N-1, N-1)) such that:

• The values along the path are strictly increasing.
• You can only move either downward or rightward at each step.

The problem requires you to use dynamic programming with recursion (or any other optimal approach) to compute the maximum length path that satisfies the conditions.

Note: The path length is defined as the number of cells visited on that path. Formally, if you visit the cells with indices \((i_1,j_1), (i_2,j_2), \dots, (i_k,j_k)\), then the length of the path is \(k\). The movement constraint means from any cell \((i,j)\), you can only move to \((i+1,j)\) or \((i,j+1)\), if the destination cell value is greater than the current cell's value.

The task is to read the grid from stdin and output the result to stdout.

inputFormat

The first line contains a single integer \(N\) representing the dimensions of the square grid. The next \(N\) lines each contain \(N\) space-separated integers representing the matrix grid.

For example:

3
1 2 3
6 5 4
7 8 9

outputFormat

Output a single integer which is the length of the longest strictly increasing path from the top-left corner to the bottom-right corner following the allowed moves.

## sample

3
1 2 3
6 5 4
7 8 9

5