Given a n*m matrix, find the maximum length path (starting from any cell) such that all cells along the path are in strictly increasing order.
We can move in 4 directions from a given cell (i, j), i.e., we can move to (i+1, j) or (i, j+1) or (i-1, j) or (i, j-1).
 
Example 1:
Input: matrix = {{1,2,9},{5,3,8},{4,6,7}}
Output: 7
Explanation: The longest increasing path is
{1,2,3,6,7,8,9}.
Example 2:
Input: matrix = {{3,4,5},{3,2,6},{2,2,1}}
Output: 4
Explanation: The longest increasing path is
{3,4,5,6}.
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function longestIncreasingPath() which takes matrix as input parameter and returns the length of the lonest increasing path.
Expected Time Complexity: O(n*m)
Expected Space Comeplxity: O(n*m)
 
Constraints:
1 <= n, m <= 100
1 <= matrix[i][j] <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

	def longestIncreasingPath(self, matrix):

		#Code here

Solutions:
class Solution:

	def longestIncreasingPath(self, grid):
		dp = [[-1] * len(grid[0]) for i in range(len(grid))]

		def dfs(i, j, prev):
			if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])) or (grid[i][j] <= prev):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			count = 1
			count += max(dfs(i + 1, j, grid[i][j]), dfs(i - 1, j, grid[i][j]), dfs(i, j + 1, grid[i][j]), dfs(i, j - 1, grid[i][j]))
			dp[i][j] = count
			return dp[i][j]
		prev = 0
		maxi = -1
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				maxi = max(maxi, dfs(i, j, -1))
		return maxi


class Solution:

	def longestIncreasingPath(self, matrix):
		R = len(matrix)
		C = len(matrix[0])
		dp = [[-1] * C for _ in range(R)]

		def traverse(r, c):
			if dp[r][c] != -1:
				return dp[r][c]
			top = left = right = bottom = 0
			if r > 0 and matrix[r][c] < matrix[r - 1][c]:
				top = traverse(r - 1, c)
			if r < R - 1 and matrix[r][c] < matrix[r + 1][c]:
				bottom = traverse(r + 1, c)
			if c > 0 and matrix[r][c] < matrix[r][c - 1]:
				left = traverse(r, c - 1)
			if c < C - 1 and matrix[r][c] < matrix[r][c + 1]:
				right = traverse(r, c + 1)
			dp[r][c] = 1 + max(top, left, bottom, right)
			return dp[r][c]
		res = 0
		for r in range(R):
			for c in range(C):
				res = max(res, traverse(r, c))
		return res


from itertools import product

class Solution:

	def solve(self, n, m, mat, i, j, dp):
		if i == n or j == m or i < 0 or (j < 0):
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		up = right = left = down = 0
		if j > 0 and mat[i][j] < mat[i][j - 1]:
			left = self.solve(n, m, mat, i, j - 1, dp)
		if j < m - 1 and mat[i][j] < mat[i][j + 1]:
			right = self.solve(n, m, mat, i, j + 1, dp)
		if i > 0 and mat[i][j] < mat[i - 1][j]:
			up = self.solve(n, m, mat, i - 1, j, dp)
		if i < n - 1 and mat[i][j] < mat[i + 1][j]:
			down = self.solve(n, m, mat, i + 1, j, dp)
		dp[i][j] = 1 + max(up, right, down, left)
		return dp[i][j]

	def longestIncreasingPath(self, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		res = 1
		dp = [[-1] * m for _ in range(n)]
		for i in range(n):
			for j in range(m):
				res = max(res, self.solve(n, m, matrix, i, j, dp))
		return res


class Solution:
	dp = [[None for i in range(0, 101)] for j in range(0, 101)]

	def path(self, matrix, i, j, m, n, past_paths, count):
		if self.dp[i][j] is not None:
			return count + self.dp[i][j]
		if i > m - 1 or j > n - 1 or i < 0 or (j < 0):
			return count
		left = count
		right = count
		up = count
		down = count
		if j - 1 >= 0 and matrix[i][j - 1] > matrix[i][j] and ((i, j - 1) not in past_paths):
			left = self.path(matrix, i, j - 1, m, n, past_paths + [(i, j - 1)], count + 1)
		if j + 1 < n and matrix[i][j + 1] > matrix[i][j] and ((i, j + 1) not in past_paths):
			right = self.path(matrix, i, j + 1, m, n, past_paths + [(i, j + 1)], count + 1)
		if i - 1 >= 0 and matrix[i - 1][j] > matrix[i][j] and ((i - 1, j) not in past_paths):
			up = self.path(matrix, i - 1, j, m, n, past_paths + [(i - 1, j)], count + 1)
		if i + 1 < m and matrix[i + 1][j] > matrix[i][j] and ((i + 1, j) not in past_paths):
			down = self.path(matrix, i + 1, j, m, n, past_paths + [(i + 1, j)], count + 1)
		self.dp[i][j] = max(left, right, up, down) - count
		return max(left, right, up, down)

	def longestIncreasingPath(self, matrix):
		maximum = 0
		self.dp = [[None for i in range(0, 101)] for j in range(0, 101)]
		for i in range(0, len(matrix)):
			for j in range(0, len(matrix[0])):
				ans = self.path(matrix, i, j, len(matrix), len(matrix[0]), list() + [(i, j)], 1)
				if ans > maximum:
					maximum = ans
		return maximum


class Solution:
	path = [[-1] * 100 for _ in range(100)]

	def find(self, matrix, start):
		(n, m) = (len(matrix), len(matrix[0]))
		(i, j) = (start[0], start[1])
		if self.path[i][j] != -1:
			return self.path[i][j]
		self.path[i][j] = 1
		v = matrix[i][j]
		if i > 0:
			up = matrix[i - 1][j]
			if up > v:
				self.path[i][j] = max(1 + self.find(matrix, (i - 1, j)), self.path[i][j])
		if i < n - 1:
			down = matrix[i + 1][j]
			if down > v:
				self.path[i][j] = max(1 + self.find(matrix, (i + 1, j)), self.path[i][j])
		if j > 0:
			left = matrix[i][j - 1]
			if left > v:
				self.path[i][j] = max(1 + self.find(matrix, (i, j - 1)), self.path[i][j])
		if j < m - 1:
			right = matrix[i][j + 1]
			if right > v:
				self.path[i][j] = max(1 + self.find(matrix, (i, j + 1)), self.path[i][j])
		return self.path[i][j]

	def longestIncreasingPath(self, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		for i in range(n):
			for j in range(m):
				self.path[i][j] = -1
		ans = -1
		for i in range(n):
			for j in range(m):
				if self.path[i][j] == -1:
					self.find(matrix, (i, j))
				ans = max(ans, self.path[i][j])
		return ans


class Solution:

	def longestIncreasingPath(self, mat):
		n = len(mat)
		m = len(mat[0])
		dp = {}

		def dfs(i, j):
			if (i, j) in dp:
				return dp[i, j]
			for (di, dj) in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
				if 0 <= i + di < n and 0 <= j + dj < m and (mat[i][j] < mat[i + di][j + dj]):
					dp[i, j] = max(dp.get((i, j), 0), dfs(i + di, j + dj))
			dp[i, j] = dp.get((i, j), 0) + 1
			return dp[i, j]
		ans = 0
		for i in range(n):
			for j in range(m):
				ans = max(ans, dfs(i, j))
		return ans


def issafe(i, j, mat):
	if i < 0 or j < 0 or i >= len(mat) or (j >= len(mat[0])):
		return 0
	return 1

def rec(mat, i, j, dp):
	if dp[i][j] != -1:
		return dp[i][j]
	ans = 1
	if issafe(i + 1, j, mat) and mat[i + 1][j] > mat[i][j]:
		ans = max(ans, rec(mat, i + 1, j, dp) + 1)
	if issafe(i - 1, j, mat) and mat[i - 1][j] > mat[i][j]:
		ans = max(ans, rec(mat, i - 1, j, dp) + 1)
	if issafe(i, j + 1, mat) and mat[i][j + 1] > mat[i][j]:
		ans = max(ans, rec(mat, i, j + 1, dp) + 1)
	if issafe(i, j - 1, mat) and mat[i][j - 1] > mat[i][j]:
		ans = max(ans, rec(mat, i, j - 1, dp) + 1)
	dp[i][j] = ans
	return dp[i][j]

class Solution:

	def longestIncreasingPath(self, matrix):
		dp = [[-1 for i in range(len(matrix[0]))] for j in range(len(matrix))]
		res = 1
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if dp[i][j] == -1:
					res = max(res, rec(matrix, i, j, dp))
		return res


class Solution:

	def solve(self, n, m, mat, i, j, dp):
		if i == n or j == m or i < 0 or (j < 0):
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		up = right = left = down = 0
		if j > 0 and mat[i][j] < mat[i][j - 1]:
			left = self.solve(n, m, mat, i, j - 1, dp)
		if j < m - 1 and mat[i][j] < mat[i][j + 1]:
			right = self.solve(n, m, mat, i, j + 1, dp)
		if i > 0 and mat[i][j] < mat[i - 1][j]:
			up = self.solve(n, m, mat, i - 1, j, dp)
		if i < n - 1 and mat[i][j] < mat[i + 1][j]:
			down = self.solve(n, m, mat, i + 1, j, dp)
		dp[i][j] = 1 + max(up, right, down, left)
		return dp[i][j]

	def longestIncreasingPath(self, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		maxi = 1
		dp = [[-1] * m for _ in range(n)]
		for i in range(n):
			for j in range(m):
				maxi = max(maxi, self.solve(n, m, matrix, i, j, dp))
		return maxi


class Solution:

	def longestIncreasingPath(self, matrix):
		r = len(matrix)
		c = len(matrix[0])
		directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		longests = [[0] * c for _ in range(r)]

		def visit(i, j):
			res = 1
			for direct in directions:
				new_r = direct[0] + i
				new_c = direct[1] + j
				if 0 <= new_r <= r - 1 and 0 <= new_c <= c - 1:
					if matrix[new_r][new_c] >= matrix[i][j] + 1:
						if longests[new_r][new_c] == 0:
							visit(new_r, new_c)
						this_len = longests[new_r][new_c] + 1
						res = max(res, this_len)
			longests[i][j] = res
		longest_incr = 1
		for i in range(r):
			for j in range(c):
				visit(i, j)
		for i in range(r):
			for j in range(c):
				longest_incr = max(longests[i][j], longest_incr)
		return longest_incr


class Solution:

	def longestIncreasingPath(self, matrix):
		dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		self.paths = [[-1 for j in range(m)] for i in range(n)]
		self.mat = matrix
		(self.m, self.n) = (m, n)
		res = 1
		for i in range(n):
			for j in range(m):
				val = self.longest_inc_path_sub(i, j, dirs)
				res = max(res, val)
		return res

	def longest_inc_path_sub(self, i, j, dirs):
		if self.paths[i][j] == -1:
			res = 1
			for (dI, dJ) in dirs:
				(nI, nJ) = (i + dI, j + dJ)
				if self.is_valid(nI, nJ) and self.mat[i][j] < self.mat[nI][nJ]:
					val = self.longest_inc_path_sub(nI, nJ, dirs)
					res = max(res, val + 1)
			self.paths[i][j] = res
		return self.paths[i][j]

	def is_valid(self, i, j):
		boolI = i >= 0 and i < self.n
		boolJ = j >= 0 and j < self.m
		return boolI and boolJ


class Solution:

	def dfs(self, matrix, i, j, n, m, vis):
		if i < 0 or i >= n or j < 0 or (j >= m):
			return 0
		if vis[i][j] != -1:
			return vis[i][j]
		val = matrix[i][j]
		ans = [0, 0, 0, 0]
		if i - 1 >= 0 and matrix[i - 1][j] > val:
			ans[0] = self.dfs(matrix, i - 1, j, n, m, vis) + 1
		if i + 1 < n and matrix[i + 1][j] > val:
			ans[1] = self.dfs(matrix, i + 1, j, n, m, vis) + 1
		if j - 1 >= 0 and matrix[i][j - 1] > val:
			ans[2] = self.dfs(matrix, i, j - 1, n, m, vis) + 1
		if j + 1 < m and matrix[i][j + 1] > val:
			ans[3] = self.dfs(matrix, i, j + 1, n, m, vis) + 1
		vis[i][j] = max(max(ans), 1)
		return vis[i][j]

	def longestIncreasingPath(self, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		vis = [[-1 for _ in range(m)] for _ in range(n)]
		ans = 1
		for i in range(n):
			for j in range(m):
				ans1 = self.dfs(matrix, i, j, n, m, vis)
				ans = max(ans, ans1)
		return ans


class Solution:

	def longestIncreasingPath(self, matrix):
		rows = len(matrix)
		cols = len(matrix[0])
		dp = [[-1 for _ in range(cols)] for _ in range(rows)]
		ans = 0
		for i in range(rows):
			for j in range(cols):
				if dp[i][j] == -1:
					self.dfs(matrix, i, j, dp, rows, cols)
				ans = max(ans, dp[i][j])
		return ans

	def dfs(self, matrix, i, j, dp, rows, cols):
		if dp[i][j] != -1:
			return dp[i][j]
		dp[i][j] = 1
		if i > 0 and matrix[i][j] > matrix[i - 1][j]:
			dp[i][j] = max(dp[i][j], self.dfs(matrix, i - 1, j, dp, rows, cols) + 1)
		if i < rows - 1 and matrix[i][j] > matrix[i + 1][j]:
			dp[i][j] = max(dp[i][j], self.dfs(matrix, i + 1, j, dp, rows, cols) + 1)
		if j > 0 and matrix[i][j] > matrix[i][j - 1]:
			dp[i][j] = max(dp[i][j], self.dfs(matrix, i, j - 1, dp, rows, cols) + 1)
		if j < cols - 1 and matrix[i][j] > matrix[i][j + 1]:
			dp[i][j] = max(dp[i][j], self.dfs(matrix, i, j + 1, dp, rows, cols) + 1)
		return dp[i][j]


class Solution:

	def longestIncreasingPath(self, l):
		(n, m) = (len(l), len(l[0]))
		d = {}
		dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]

		def dfs(i, j, p):
			if i < 0 or j < 0 or i == n or (j == m) or (l[i][j] <= p):
				return 0
			if d.get((i, j)):
				return d[i, j]
			x = 0
			for (p, q) in dir:
				x = max(x, dfs(i + p, j + q, l[i][j]))
			d[i, j] = x + 1
			return d[i, j]
		x = 1
		for i in range(n):
			for j in range(m):
				x = max(x, dfs(i, j, -1))
		return x


class Solution:

	def longestIncreasingPath(self, matrix):
		r = len(matrix)
		c = len(matrix[0])
		mat = {}

		def helper(i, j, prev_value):
			if i < 0 or i == r or j < 0 or (j == c) or (matrix[i][j] <= prev_value):
				return 0
			if (i, j) in mat:
				return mat[i, j]
			final = 1
			final = max(final, 1 + helper(i - 1, j, matrix[i][j]))
			final = max(final, 1 + helper(i + 1, j, matrix[i][j]))
			final = max(final, 1 + helper(i, j - 1, matrix[i][j]))
			final = max(final, 1 + helper(i, j + 1, matrix[i][j]))
			mat[i, j] = final
			return final
		for i in range(r):
			for j in range(c):
				helper(i, j, -1)
		return max(mat.values())


class Solution:

	def longestIncreasingPath(self, matrix):
		r = len(matrix)
		p = len(matrix[0])
		dp = [[0] * p for _ in range(r)]
		m = 0

		def paths(i, j, prev):
			if i < 0 or i >= r or j < 0 or (j >= p) or (prev is not None and matrix[i][j] <= prev):
				return 0
			if dp[i][j] != 0:
				return dp[i][j]
			c = 0
			c = max(c, paths(i + 1, j, matrix[i][j]))
			c = max(c, paths(i - 1, j, matrix[i][j]))
			c = max(c, paths(i, j + 1, matrix[i][j]))
			c = max(c, paths(i, j - 1, matrix[i][j]))
			dp[i][j] = c + 1
			return c + 1
		for i in range(r):
			for j in range(p):
				m = max(m, paths(i, j, None))
		return m


from itertools import product

class Solution:

	def longestIncreasingPath(self, mat):
		(n, m) = (len(mat), len(mat[0]))
		dp = [[-1] * m for i in range(n)]

		def dfs(i, j, n, m, prev):
			if i < 0 or i >= n or j < 0 or (j >= m):
				return 0
			if mat[i][j] <= prev:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			dp[i][j] = 1 + max(dfs(i + 1, j, n, m, mat[i][j]), dfs(i - 1, j, n, m, mat[i][j]), dfs(i, j + 1, n, m, mat[i][j]), dfs(i, j - 1, n, m, mat[i][j]))
			return dp[i][j]
		ans = 0
		for (i, j) in product(range(n), range(m)):
			ans = max(ans, dfs(i, j, n, m, mat[i][j] - 1))
		return ans


class Solution:

	def longestIncreasingPath(self, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		dp = [[-1 for i in range(m)] for j in range(n)]

		def dfs(i, j):
			if dp[i][j] != -1:
				return dp[i][j]
			dp[i][j] = 1
			a = []
			for (u, v) in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:
				if 0 <= u < n and 0 <= v < m and (matrix[u][v] > matrix[i][j]):
					a.append(dfs(u, v))
			if a:
				dp[i][j] += max(a)
			return dp[i][j]
		ans = 1
		for i in range(n):
			for j in range(m):
				ans = max(ans, dfs(i, j))
		return ans


class Solution:

	def longestIncreasingPath(self, m):
		dp = [[-1] * len(m[0]) for i in range(len(m))]

		def findpath(i, j):
			if i >= len(m) or j >= len(m[0]):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			visited[i][j] = 1
			up = down = left = right = 0
			if i - 1 >= 0 and m[i][j] < m[i - 1][j]:
				up = 1 + findpath(i - 1, j)
			if i + 1 < len(m) and m[i][j] < m[i + 1][j]:
				down = 1 + findpath(i + 1, j)
			if j - 1 >= 0 and m[i][j] < m[i][j - 1]:
				left = 1 + findpath(i, j - 1)
			if j + 1 < len(m[0]) and m[i][j] < m[i][j + 1]:
				right = 1 + findpath(i, j + 1)
			dp[i][j] = max(up, down, left, right)
			return max(up, down, left, right)
		visited = [[-1] * len(m[0]) for i in range(len(m))]
		maxl = 0
		for i in range(len(m)):
			for j in range(len(m[0])):
				val = findpath(i, j)
				maxl = max(maxl, 1 + val)
		return maxl


class Solution:

	def longestIncreasingPath(self, matrix):
		(m, n) = (len(matrix), len(matrix[0]))
		dp = [[-1 for j in range(n)] for i in range(m)]
		res = 1

		def helper(i, j, m, n, matrix, dp):
			if dp[i][j] != -1:
				return dp[i][j]
			ans = [0, 0, 0, 0]
			if i - 1 >= 0 and matrix[i - 1][j] > matrix[i][j]:
				ans[0] = helper(i - 1, j, m, n, matrix, dp) + 1
			if i + 1 < m and matrix[i + 1][j] > matrix[i][j]:
				ans[1] = helper(i + 1, j, m, n, matrix, dp) + 1
			if j - 1 >= 0 and matrix[i][j - 1] > matrix[i][j]:
				ans[2] = helper(i, j - 1, m, n, matrix, dp) + 1
			if j + 1 < n and matrix[i][j + 1] > matrix[i][j]:
				ans[3] = helper(i, j + 1, m, n, matrix, dp) + 1
			dp[i][j] = max(1, max(ans))
			return dp[i][j]
		for i in range(m):
			for j in range(n):
				res_tmp = helper(i, j, m, n, matrix, dp)
				res = max(res, res_tmp)
		return res


class Solution:

	def longestIncreasingPath(self, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		ans = 0
		mem = [[-1] * m for i in range(n)]
		for i in range(n):
			for j in range(m):
				ans1 = self.dfs(matrix, i, j, n, m, mem)
				ans = max(ans1, ans)
		return ans

	def dfs(self, matirx, i, j, n, m, mem):
		if i < 0 or j < 0 or i >= n or (j >= m):
			return 0
		if mem[i][j] != -1:
			return mem[i][j]
		value = matrix[i][j]
		ans = [0, 0, 0, 0]
		if i - 1 >= 0 and matrix[i - 1][j] > value:
			ans[0] = self.dfs(matrix, i - 1, j, n, m, mem) + 1
		if j - 1 >= 0 and matrix[i][j - 1] > value:
			ans[1] = self.dfs(matrix, i, j - 1, n, m, mem) + 1
		if i + 1 < n and matrix[i + 1][j] > value:
			ans[2] = self.dfs(matrix, i + 1, j, n, m, mem) + 1
		if j + 1 < m and matrix[i][j + 1] > value:
			ans[3] = self.dfs(matrix, i, j + 1, n, m, mem) + 1
		mem[i][j] = max(max(ans), 1)
		return mem[i][j]


class Solution:

	def longestIncreasingPath(self, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		dpArr = [[-1] * m for i in range(n)]

		def dfs(i, j, preval):
			if i < 0 or i >= n or j < 0 or (j >= m) or (matrix[i][j] <= preval):
				return 0
			if dpArr[i][j] != -1:
				return dpArr[i][j]
			res = 1
			res = max(res, 1 + dfs(i + 1, j, matrix[i][j]))
			res = max(res, 1 + dfs(i - 1, j, matrix[i][j]))
			res = max(res, 1 + dfs(i, j + 1, matrix[i][j]))
			res = max(res, 1 + dfs(i, j - 1, matrix[i][j]))
			dpArr[i][j] = res
			return res
		ans = 1
		for i in range(n):
			for j in range(m):
				dfs(i, j, -1)
			ans = max(ans, max(dpArr[i]))
		return ans


class Solution:

	def lip_util(self, i, j, matrix, visited):
		n = len(matrix)
		m = len(matrix[0])
		if visited[i][j] != -1:
			return visited[i][j]
		max_len = 1
		dxy = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		for (dx, dy) in dxy:
			new_i = i + dx
			new_j = j + dy
			if new_i >= 0 and new_i < n and (new_j >= 0) and (new_j < m) and (matrix[new_i][new_j] > matrix[i][j]):
				max_len = max(max_len, 1 + self.lip_util(new_i, new_j, matrix, visited))
		visited[i][j] = max_len
		return max_len

	def longestIncreasingPath(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		visited = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]
		max_len = 1
		for row in range(n):
			for col in range(m):
				if visited[row][col] == -1:
					max_len = max(max_len, self.lip_util(row, col, matrix, visited))
		return max_len


class Solution:

	def dfs(self, i, j, n, m, grid, dp, prev, vis):
		if i < 0 or j < 0 or i >= n or (j >= m) or (grid[i][j] <= prev) or (vis[i][j] != 0):
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		vis[i][j] = 1
		curr_max = 0
		a = self.dfs(i + 1, j, n, m, grid, dp, grid[i][j], vis)
		b = self.dfs(i - 1, j, n, m, grid, dp, grid[i][j], vis)
		c = self.dfs(i, j + 1, n, m, grid, dp, grid[i][j], vis)
		d = self.dfs(i, j - 1, n, m, grid, dp, grid[i][j], vis)
		curr_max = 1 + max(a, max(b, max(c, d)))
		dp[i][j] = curr_max
		vis[i][j] = 0
		return dp[i][j]

	def longestIncreasingPath(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		if n == 0 or m == 0:
			return 0
		dp = [[-1 for i in range(m)] for j in range(n)]
		vis = [[0 for i in range(m)] for j in range(n)]
		Max = 0
		for i in range(n):
			for j in range(m):
				Max = max(Max, self.dfs(i, j, n, m, matrix, dp, -1, vis))
		return Max


class Solution:

	def longestIncreasingPath(self, matrix):
		n = len(matrix)
		m = len(matrix[0])

		def dfs(i, j, dp, vis):
			if vis[i][j]:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			vis[i][j] = 1
			diff = [[0, 1], [0, -1], [1, 0], [-1, 0]]
			temp = 0
			for (dx, dy) in diff:
				x = i + dx
				y = j + dy
				if x < 0 or y < 0 or x >= n or (y >= m):
					continue
				if matrix[x][y] > matrix[i][j]:
					temp = max(temp, 1 + dfs(x, y, dp, vis))
			dp[i][j] = temp
			vis[i][j] = 0
			return temp
		vis = [[0] * m for i in range(n)]
		dp = [[-1] * m for i in range(n)]
		ans = 0
		for i in range(n):
			for j in range(m):
				if not vis[i][j]:
					dfs(i, j, dp, vis)
					ans = max(ans, dp[i][j])
		return ans + 1


def f(A, x, y, dp):
	N = len(A)
	M = len(A[0])
	if dp[x][y] != -1:
		return dp[x][y]
	dx = [1, -1, 0, 0]
	dy = [0, 0, 1, -1]
	ans = 0
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		if nx >= 0 and nx < N and (ny >= 0) and (ny < M) and (A[nx][ny] > A[x][y]):
			ans = max(ans, 1 + f(A, nx, ny, dp))
	ans = max(ans, 1)
	dp[x][y] = ans
	return ans

class Solution:

	def longestIncreasingPath(self, A):
		N = len(A)
		M = len(A[0])
		dp = [[-1 for i in range(M)] for i in range(N)]
		ans = 0
		for i in range(N):
			for j in range(M):
				ans = max(ans, f(A, i, j, dp))
		return ans


class Solution:

	def longestIncreasingPath(self, matrix):

		def explore(mat, i, j, count=0):
			if not 0 <= i < len(mat) and (not 0 <= j < len(mat[0])):
				return 0
			if (i, j) in explore.memo:
				return explore.memo[i, j]
			(w, x, y, z) = (0, 0, 0, 0)
			if 0 <= i + 1 < len(mat) and mat[i][j] < mat[i + 1][j]:
				x = 1 + explore(mat, i + 1, j)
			if 0 <= j + 1 < len(mat[0]) and mat[i][j] < mat[i][j + 1]:
				y = 1 + explore(mat, i, j + 1)
			if 0 <= j - 1 < len(mat[0]) and mat[i][j] < mat[i][j - 1]:
				z = 1 + explore(mat, i, j - 1)
			if 0 <= i - 1 < len(mat) and mat[i][j] < mat[i - 1][j]:
				w = 1 + explore(mat, i - 1, j)
			explore.memo[i, j] = max(w, x, y, z)
			return explore.memo[i, j]
		explore.memo = {}
		ans = 0
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				r = explore(matrix, i, j)
				if r > ans:
					ans = r
		return ans + 1


class Solution:

	def longestIncreasingPath(self, matrix):
		(m, n) = (len(matrix), len(matrix[0]))
		memo = {}

		def dfs(i, j):
			if i < 0 or i >= m or j < 0 or (j >= n):
				return 0
			if (i, j) in memo:
				return memo[i, j]
			res = 0
			for (di, dj) in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
				(x, y) = (i + di, j + dj)
				if x < 0 or x >= m or y < 0 or (y >= n) or (matrix[i][j] <= matrix[x][y]):
					continue
				res = max(res, dfs(x, y) + 1)
			memo[i, j] = res
			return res
		res = float('-inf')
		for i in range(m):
			for j in range(n):
				res = max(res, dfs(i, j) + 1)
		return res


class Solution:

	def longestIncreasingPath(self, l):
		d = {}
		(n, m) = (len(l), len(l[0]))
		z = 0

		def dfs(i, j, p):
			if i < 0 or j < 0 or i == n or (j == m) or (l[i][j] <= p):
				return 0
			if d.get((i, j), 0):
				return d[i, j]
			d[i, j] = max(dfs(i - 1, j, l[i][j]), dfs(i + 1, j, l[i][j]), dfs(i, j - 1, l[i][j]), dfs(i, j + 1, l[i][j])) + 1
			return d[i, j]
		for i in range(n):
			for j in range(m):
				if not d.get((i, j), 0):
					z = max(z, dfs(i, j, -1))
		return z


class Solution:

	def longestIncreasingPath(self, x):
		(m, n) = (len(x), len(x[0]))

		def f(i, j):
			if (i, j) in dp:
				return dp[i, j]
			ans = 0
			for (d, e) in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
				if 0 <= d < m and 0 <= e < n and (x[i][j] < x[d][e]):
					ans = max(ans, f(d, e))
			dp[i, j] = ans + 1
			return ans + 1
		dp = {}
		return max((max((f(i, j) for i in range(m))) for j in range(n)))


class Solution:

	def longestIncreasingPath(self, matrix):
		m = len(matrix)
		n = len(matrix[0])
		dp = [[-1] * n for _ in range(m)]

		def dfs(i, j, prev):
			if i < 0 or j < 0 or i >= m or (j >= n) or (prev >= matrix[i][j]):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			top = dfs(i - 1, j, matrix[i][j])
			right = dfs(i, j + 1, matrix[i][j])
			left = dfs(i, j - 1, matrix[i][j])
			bottom = dfs(i + 1, j, matrix[i][j])
			dp[i][j] = max(top, right, left, bottom) + 1
			return dp[i][j]
		mx = -1
		for i in range(m):
			for j in range(n):
				mx = max(mx, dfs(i, j, -1))
		return mx


class Solution:

	def longestIncreasingPath(self, matrix):

		def recursive(matrix, n, m, visited, i, j, prev=-1):
			if i < 0 or i >= n or j < 0 or (j >= m):
				return 0
			if visited[i][j] != -1:
				return visited[i][j]
			if matrix[i][j] > prev:
				path = 0
				a = recursive(matrix, n, m, visited, i + 1, j, matrix[i][j])
				b = recursive(matrix, n, m, visited, i, j + 1, matrix[i][j])
				c = recursive(matrix, n, m, visited, i - 1, j, matrix[i][j])
				d = recursive(matrix, n, m, visited, i, j - 1, matrix[i][j])
				a = a if a > 0 and matrix[i][j] < matrix[i + 1][j] else 0
				b = b if b > 0 and matrix[i][j] < matrix[i][j + 1] else 0
				c = c if c > 0 and matrix[i][j] < matrix[i - 1][j] else 0
				d = d if d > 0 and matrix[i][j] < matrix[i][j - 1] else 0
				path = 1 + max(max(a, b), max(c, d))
				visited[i][j] = path
				return visited[i][j]
			return 0
		max_len = 0
		(n, m) = (len(matrix), len(matrix[0]))
		visited = [[-1 for i in range(m)] for j in range(n)]
		for i in range(n):
			for j in range(m):
				cur_len = recursive(matrix, n, m, visited, i, j)
				max_len = max(cur_len, max_len)
		return max_len


class Solution:

	def longestIncreasingPath(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		dp = [[-1 for i in range(m)] for j in range(n)]
		directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

		def solve(i, j):
			if dp[i][j] == -1:
				mx = 1
				for (x, y) in directions:
					ni = i + x
					nj = j + y
					if ni < 0 or nj < 0 or ni >= n or (nj >= m) or (matrix[ni][nj] <= matrix[i][j]):
						continue
					mx = max(mx, 1 + solve(ni, nj))
				dp[i][j] = mx
			return dp[i][j]
		ans = 1
		for i in range(n):
			for j in range(m):
				if dp[i][j] == -1:
					ans = max(ans, solve(i, j))
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m) = input().split()
		n = int(n)
		m = int(m)
		matrix = []
		for _ in range(n):
			matrix.append(list(map(int, input().split())))
		obj = Solution()
		ans = obj.longestIncreasingPath(matrix)
		print(ans)


class Solution:

	def findlongpath(self, i, j, l, d):
		if i < 0 or i >= n or j < 0 or (j >= m):
			return 0
		if d[i][j] != -1:
			return d[i][j]
		(x, y, z, w) = (-1, -1, -1, -1)
		if j < m - 1 and l[i][j] < l[i][j + 1]:
			x = 1 + self.findlongpath(i, j + 1, l, d)
		if j > 0 and l[i][j] < l[i][j - 1]:
			y = 1 + self.findlongpath(i, j - 1, l, d)
		if i < n - 1 and l[i][j] < l[i + 1][j]:
			z = 1 + self.findlongpath(i + 1, j, l, d)
		if i > 0 and l[i][j] < l[i - 1][j]:
			w = 1 + self.findlongpath(i - 1, j, l, d)
		d[i][j] = max(x, max(y, max(z, max(w, 1))))
		return d[i][j]

	def longestIncreasingPath(self, matrix):
		result = -1
		d = [[-1 for i in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				if d[i][j] == -1:
					d[i][j] = self.findlongpath(i, j, matrix, d)
				result = max(result, d[i][j])
		return result
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m) = input().split()
		n = int(n)
		m = int(m)
		matrix = []
		for _ in range(n):
			matrix.append(list(map(int, input().split())))
		obj = Solution()
		ans = obj.longestIncreasingPath(matrix)
		print(ans)


class Solution:

	def dfs(self, value_mat, i, j, visited, val):
		if i >= len(self.mat) or i < 0 or j >= len(self.mat[0]) or (j < 0):
			return 0
		if self.mat[i][j] <= val:
			return 0
		if not visited[i][j]:
			visited[i][j] = True
			value_mat[i][j] = max(self.dfs(value_mat, i - 1, j, visited, self.mat[i][j]), self.dfs(value_mat, i + 1, j, visited, self.mat[i][j]), self.dfs(value_mat, i, j - 1, visited, self.mat[i][j]), self.dfs(value_mat, i, j + 1, visited, self.mat[i][j])) + 1
			return value_mat[i][j]
		else:
			return value_mat[i][j]

	def longestIncreasingPath(self, matrix):
		self.mat = matrix
		visited = [[False for i in range(len(matrix[0]))] for j in range(len(matrix))]
		value_mat = [[0 for i in range(len(matrix[0]))] for j in range(len(matrix))]
		max_value = -float('inf')
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				max_value = max(self.dfs(value_mat, i, j, visited, -1), max_value)
		return max_value
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m) = input().split()
		n = int(n)
		m = int(m)
		matrix = []
		for _ in range(n):
			matrix.append(list(map(int, input().split())))
		obj = Solution()
		ans = obj.longestIncreasingPath(matrix)
		print(ans)


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def longestIncreasingPath(self, l):
		(n, m) = (len(l), len(l[0]))
		z = 0
		d = {}

		def dfs(i, j, x):
			if i < 0 or i == n or j < 0 or (j == m) or (l[i][j] <= x):
				return 0
			if d.get((i, j), 0):
				return d[i, j]
			d[i, j] = max(dfs(i, j - 1, l[i][j]), dfs(i, j + 1, l[i][j]), dfs(i - 1, j, l[i][j]), dfs(i + 1, j, l[i][j])) + 1
			return d[i, j]
		for i in range(n):
			for j in range(m):
				z = max(z, dfs(i, j, -1))
		return z
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m) = input().split()
		n = int(n)
		m = int(m)
		matrix = []
		for _ in range(n):
			matrix.append(list(map(int, input().split())))
		obj = Solution()
		ans = obj.longestIncreasingPath(matrix)
		print(ans)


from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def findLongestFromACell(self, i, j, mat, dp):
		m = len(matrix)
		n = len(matrix[0])
		if i < 0 or i >= m or j < 0 or (j >= n):
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		(x, y, z, w) = (-1, -1, -1, -1)
		if j < n - 1 and mat[i][j] < mat[i][j + 1]:
			x = 1 + self.findLongestFromACell(i, j + 1, mat, dp)
		if j > 0 and mat[i][j] < mat[i][j - 1]:
			y = 1 + self.findLongestFromACell(i, j - 1, mat, dp)
		if i > 0 and mat[i][j] < mat[i - 1][j]:
			z = 1 + self.findLongestFromACell(i - 1, j, mat, dp)
		if i < m - 1 and mat[i][j] < mat[i + 1][j]:
			w = 1 + self.findLongestFromACell(i + 1, j, mat, dp)
		dp[i][j] = max(x, y, z, w, 1)
		return dp[i][j]

	def longestIncreasingPath(self, matrix):
		m = len(matrix)
		n = len(matrix[0])
		result = 1
		dp = [[-1 for i in range(n)] for j in range(m)]
		for i in range(m):
			for j in range(n):
				if dp[i][j] == -1:
					self.findLongestFromACell(i, j, matrix, dp)
				result = max(result, dp[i][j])
		return result
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m) = input().split()
		n = int(n)
		m = int(m)
		matrix = []
		for _ in range(n):
			matrix.append(list(map(int, input().split())))
		obj = Solution()
		ans = obj.longestIncreasingPath(matrix)
		print(ans)


from collections import deque

class Solution:

	def longestIncreasingPath(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		ans = 0
		mat = [[0 for i in range(m)] for j in range(n)]

		def dijkstra(i, j):
			mat[i][j] = 1
			q = deque()
			q.append([-1, i, j])
			while q:
				(wt, nodex, nodey) = q.popleft()
				wt = -1 * wt
				if nodex + 1 < n:
					if matrix[nodex + 1][nodey] > matrix[nodex][nodey] and wt + 1 > mat[nodex + 1][nodey]:
						mat[nodex + 1][nodey] = wt + 1
						q.append([-(wt + 1), nodex + 1, nodey])
				if nodex - 1 >= 0:
					if matrix[nodex - 1][nodey] > matrix[nodex][nodey] and wt + 1 > mat[nodex - 1][nodey]:
						mat[nodex - 1][nodey] = wt + 1
						q.append([-(wt + 1), nodex - 1, nodey])
				if nodey + 1 < m:
					if matrix[nodex][nodey + 1] > matrix[nodex][nodey] and wt + 1 > mat[nodex][nodey + 1]:
						mat[nodex][nodey + 1] = wt + 1
						q.append([-(wt + 1), nodex, nodey + 1])
				if nodey - 1 >= 0:
					if matrix[nodex][nodey - 1] > matrix[nodex][nodey] and wt + 1 > mat[nodex][nodey - 1]:
						mat[nodex][nodey - 1] = wt + 1
						q.append([-(wt + 1), nodex, nodey - 1])
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 0:
					dijkstra(i, j)
		ans = 0
		for i in range(n):
			for j in range(m):
				ans = max(ans, mat[i][j])
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m) = input().split()
		n = int(n)
		m = int(m)
		matrix = []
		for _ in range(n):
			matrix.append(list(map(int, input().split())))
		obj = Solution()
		ans = obj.longestIncreasingPath(matrix)
		print(ans)


class Solution:

	def longestIncreasingPath(self, matrix):
		directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
		mem = [[0 for i in range(len(matrix[0]) + 1)] for j in range(len(matrix) + 1)]

		def dfs(i, j, mem):
			if mem[i][j] > 0:
				return mem[i][j]
			maxi = 0
			for dire in directions:
				newr = i + dire[0]
				newc = j + dire[1]
				if newr >= 0 and newr < n and (newc >= 0) and (newc < m) and (matrix[newr][newc] > matrix[i][j]):
					maxi = max(maxi, dfs(newr, newc, mem))
			mem[i][j] = maxi + 1
			return maxi + 1
		maxe = 0
		for i in range(n):
			for j in range(m):
				s = dfs(i, j, mem)
				if s > maxe:
					maxe = s
		return maxe


class Solution:

	def longestIncreasingPath(self, matrix):
		res = 0
		row = len(matrix)
		col = len(matrix[0])
		dp = [[0 for j in range(col)] for i in range(row)]
		dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		for i in range(row):
			for j in range(col):
				res = max(res, self.dfs(matrix, dp, dir, row, col, i, j))
		return res

	def dfs(self, matrix, dp, dir, row, col, i, j):
		res = 0
		if dp[i][j] != 0:
			return dp[i][j]
		for (x, y) in dir:
			x += i
			y += j
			if x >= 0 and x < row and (y >= 0) and (y < col) and (matrix[i][j] < matrix[x][y]):
				res = max(res, self.dfs(matrix, dp, dir, row, col, x, y))
		dp[i][j] = res + 1
		return dp[i][j]


class Solution:

	def dfs(self, matrix, i, j, ROWS, COLS, lip):
		if lip[i][j]:
			return lip[i][j]
		maxLength = 0
		for (x, y) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
			x += i
			y += j
			if 0 <= x < ROWS and 0 <= y < COLS and (matrix[x][y] > matrix[i][j]):
				maxLength = max(maxLength, self.dfs(matrix, x, y, ROWS, COLS, lip))
		lip[i][j] = maxLength + 1
		return lip[i][j]

	def longestIncreasingPath(self, matrix):
		maxPath = 0
		(ROWS, COLS) = (len(matrix), len(matrix[0]))
		lip = [[0] * COLS for _ in range(ROWS)]
		for i in range(ROWS):
			for j in range(COLS):
				maxPath = max(maxPath, self.dfs(matrix, i, j, ROWS, COLS, lip))
		return maxPath


import sys

def rec(dp, i, j, n, m, matrix):
	if dp[i][j] != -1:
		return dp[i][j]
	ans = 1
	if i < n - 1 and matrix[i + 1][j] > matrix[i][j]:
		ans = max(ans, 1 + rec(dp, i + 1, j, n, m, matrix))
	if j < m - 1 and matrix[i][j + 1] > matrix[i][j]:
		ans = max(ans, 1 + rec(dp, i, j + 1, n, m, matrix))
	if i > 0 and matrix[i - 1][j] > matrix[i][j]:
		ans = max(ans, 1 + rec(dp, i - 1, j, n, m, matrix))
	if j > 0 and matrix[i][j - 1] > matrix[i][j]:
		ans = max(ans, 1 + rec(dp, i, j - 1, n, m, matrix))
	dp[i][j] = ans
	return ans

class Solution:

	def longestIncreasingPath(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		dp = [[-1] * m for i in range(n)]
		for i in range(n):
			for j in range(m):
				if dp[i][j] == -1:
					rec(dp, i, j, n, m, matrix)
		res = 0
		for i in range(n):
			for j in range(m):
				res = max(res, dp[i][j])
		return res


class Solution:

	def longestIncreasingPath(self, l):
		n = len(l)
		m = len(l[0])
		ans = [[-1 for _ in range(m)] for _ in range(n)]

		def dfs(i, j, t):
			if i >= n or j >= m or i < 0 or (j < 0) or (l[i][j] <= t):
				return 0
			if ans[i][j] != -1:
				return ans[i][j]
			ans[i][j] = max(dfs(i + 1, j, l[i][j]), dfs(i - 1, j, l[i][j]), dfs(i, j + 1, l[i][j]), dfs(i, j - 1, l[i][j])) + 1
			return ans[i][j]
		x = 0
		for i in range(n):
			for j in range(m):
				if ans[i][j] == -1:
					ans[i][j] = dfs(i, j, -float('inf'))
					x = max(x, ans[i][j])
		return x


class Solution:

	def longestIncreasingPath(self, matrix):
		minn = 100000
		r = None
		c = None
		n = len(matrix)
		m = len(matrix[0])
		a = []
		b = []
		for i in range(n):
			for j in range(m):
				if matrix[i][j] < minn:
					minn = matrix[i][j]
					r = i
					c = j
				b.append(0)
			a.append(b)
			b = []
		q = [[r, c]]
		size = 1
		a[r][c] = 1
		while size > 0:
			v = q.pop()
			r = v[0]
			c = v[1]
			size -= 1
			if r + 1 < n:
				if matrix[r + 1][c] > matrix[r][c] and a[r + 1][c] <= a[r][c]:
					a[r + 1][c] = a[r][c] + 1
					q.append([r + 1, c])
					size += 1
				elif a[r + 1][c] == 0:
					a[r + 1][c] = 1
					q.append([r + 1, c])
					size += 1
			if c + 1 < m:
				if matrix[r][c + 1] > matrix[r][c] and a[r][c + 1] <= a[r][c]:
					a[r][c + 1] = a[r][c] + 1
					q.append([r, c + 1])
					size += 1
				elif a[r][c + 1] == 0:
					a[r][c + 1] = 1
					q.append([r, c + 1])
					size += 1
			if r - 1 >= 0:
				if matrix[r - 1][c] > matrix[r][c] and a[r - 1][c] <= a[r][c]:
					a[r - 1][c] = a[r][c] + 1
					q.append([r - 1, c])
					size += 1
				elif a[r - 1][c] == 0:
					a[r - 1][c] = 1
					q.append([r - 1, c])
					size += 1
			if c - 1 >= 0:
				if matrix[r][c - 1] > matrix[r][c] and a[r][c - 1] <= a[r][c]:
					a[r][c - 1] = a[r][c] + 1
					q.append([r, c - 1])
					size += 1
				elif a[r][c - 1] == 0:
					a[r][c - 1] = 1
					q.append([r, c - 1])
					size += 1
		maxx = 0
		for i in range(n):
			for j in range(m):
				if a[i][j] > maxx:
					maxx = a[i][j]
		return maxx


class Solution:

	def dfs(self, i, j, dp, mat):
		if i < 0 or j < 0 or i >= len(mat) or (j >= len(mat[0])):
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		x = y = z = w = -1
		if i - 1 >= 0 and mat[i - 1][j] > mat[i][j]:
			x = 1 + self.dfs(i - 1, j, dp, mat)
		if j > 0 and mat[i][j] < mat[i][j - 1]:
			y = 1 + self.dfs(i, j - 1, dp, mat)
		if i + 1 < len(mat) and mat[i][j] < mat[i + 1][j]:
			z = 1 + self.dfs(i + 1, j, dp, mat)
		if j + 1 < len(mat[0]) and mat[i][j + 1] > mat[i][j]:
			w = 1 + self.dfs(i, j + 1, dp, mat)
		dp[i][j] = max(x, y, z, w, 1)
		return dp[i][j]

	def longestIncreasingPath(self, mat):
		dp = [[-1] * len(mat[0]) for i in range(len(mat))]
		ma = 1
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				if dp[i][j] == -1:
					dp[i][j] = self.dfs(i, j, dp, mat)
				ma = max(ma, dp[i][j])
		return ma


class Solution:

	def longestIncreasingPath(self, matrix):

		def dfs(matrix, i, j, dp, n, m, direction):
			if i < 0 or i >= n or j < 0 or (j >= m):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			cur = 1
			for d in direction:
				x = i + d[0]
				y = j + d[1]
				if x < 0 or x >= n or y < 0 or (y >= m):
					continue
				if matrix[i][j] < matrix[x][y]:
					cur = max(cur, 1 + dfs(matrix, x, y, dp, n, m, direction))
			dp[i][j] = cur
			return cur
		n = len(matrix)
		m = len(matrix[0])
		dp = [[-1 for i in range(m)] for j in range(n)]
		direction = [[0, 1], [1, 0], [-1, 0], [0, -1]]
		result = 1
		for i in range(n):
			for j in range(m):
				cur = dfs(matrix, i, j, dp, n, m, direction)
				result = max(result, cur)
		return result


class Solution:
	global paths
	paths = [[0, 1], [1, 0], [-1, 0], [0, -1]]

	def dfs(self, i, j, matrix, dp, prevVal):
		if i < 0 or j < 0 or i >= len(matrix) or (j >= len(matrix[0])) or (matrix[i][j] <= prevVal):
			return -1
		if (i, j) in dp:
			return dp[i, j]
		res = 1
		for path in paths:
			res = max(res, 1 + self.dfs(i + path[0], j + path[1], matrix, dp, matrix[i][j]))
		dp[i, j] = res
		return res

	def longestIncreasingPath(self, matrix):
		dp = {}
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				self.dfs(i, j, matrix, dp, -1)
		return max(dp.values())


class Solution:

	def longestIncreasingPath(self, mat):
		dp = [[-1 for _ in range(len(mat[0]))] for _ in range(len(mat))]

		def dfs(i, j, prev):
			if i > len(mat) - 1 or j > len(mat[0]) - 1 or i < 0 or (j < 0) or (mat[i][j] <= prev):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			ans = 1
			ans = max(ans, 1 + dfs(i + 1, j, mat[i][j]))
			ans = max(ans, 1 + dfs(i - 1, j, mat[i][j]))
			ans = max(ans, 1 + dfs(i, j - 1, mat[i][j]))
			ans = max(ans, 1 + dfs(i, j + 1, mat[i][j]))
			dp[i][j] = ans
			return ans
		ans = float('-inf')
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				curr = dfs(i, j, -1)
				ans = max(ans, curr)
		return ans


class Solution:

	def longestIncreasingPath(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		dp = {}

		def help1(i, j):
			if (i, j) in dp:
				return dp[i, j]
			p = [[1, 0], [-1, 0], [0, 1], [0, -1]]
			for (a, b) in p:
				if 0 <= i + a < n and 0 <= j + b < m and (matrix[i][j] < matrix[i + a][j + b]):
					dp[i, j] = max(dp.get((i, j), 0), help1(i + a, j + b))
			dp[i, j] = dp.get((i, j), 0) + 1
			return dp[i, j]
		ans = 0
		for i in range(n):
			for j in range(m):
				ans = max(ans, help1(i, j))
		return ans


class Solution:

	def longestIncreasingPath(self, l):
		(n, m, z) = (len(l), len(l[0]), 0)
		v = [[0] * m for i in range(n)]

		def track(i, j, p):
			if i < 0 or j < 0 or i == n or (j == m) or (l[i][j] <= p):
				return 0
			if v[i][j]:
				return v[i][j]
			x = max(track(i, j - 1, l[i][j]), track(i, j + 1, l[i][j]), track(i - 1, j, l[i][j]), track(i + 1, j, l[i][j])) + 1
			v[i][j] = x
			return x
		for i in range(n):
			for j in range(m):
				z = max(z, track(i, j, -1))
		return z


from functools import lru_cache

class Solution:

	def longestIncreasingPath(self, M):
		(m, n) = (len(M), len(M[0]))

		@lru_cache(None)
		def dp(i, j):
			val = M[i][j]
			res = 0
			directions = [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]
			for i in directions:
				(a, b) = i
				if 0 <= a < m and 0 <= b < n and (M[a][b] < val):
					res = max(res, dp(a, b))
			return 1 + res
		res = [dp(x, y) for x in range(m) for y in range(n)]
		return max(res)


class Solution:

	def longestIncreasingPath(self, matrix):
		a = len(matrix)
		b = len(matrix[0])
		dic = {}

		def DFS(i, j):
			if (i, j) in dic:
				return dic[i, j]
			for (d1, d2) in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
				if 0 <= i + d1 < a and 0 <= j + d2 < b and (matrix[i][j] < matrix[i + d1][j + d2]):
					dic[i, j] = max(dic.get((i, j), 0), DFS(i + d1, j + d2))
			dic[i, j] = dic.get((i, j), 0) + 1
			return dic[i, j]
		res = 0
		for i in range(0, a):
			for j in range(0, b):
				res = max(res, DFS(i, j))
		return res


class Solution:

	def longestIncreasingPath(self, mat):
		matrix = mat

		def dfs(i, j):
			if not dp[i][j]:
				val = matrix[i][j]
				dp[i][j] = 1 + max(dfs(i - 1, j) if i and val > matrix[i - 1][j] else 0, dfs(i + 1, j) if i < M - 1 and val > matrix[i + 1][j] else 0, dfs(i, j - 1) if j and val > matrix[i][j - 1] else 0, dfs(i, j + 1) if j < N - 1 and val > matrix[i][j + 1] else 0)
			return dp[i][j]
		if not matrix or not matrix[0]:
			return 0
		(M, N) = (len(matrix), len(matrix[0]))
		dp = [[0] * N for i in range(M)]
		return max((dfs(x, y) for x in range(M) for y in range(N)))


dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

class Solution:

	def lip(self, matrix, i, j, n, m, DP):
		best = 1
		if DP[i][j] >= 0:
			return DP[i][j]
		for k in range(4):
			(ni, nj) = (i + dx[k], j + dy[k])
			if ni >= 0 and ni < n and (nj >= 0) and (nj < m):
				if matrix[i][j] < matrix[ni][nj]:
					p = self.lip(matrix, ni, nj, n, m, DP)
					best = max(best, 1 + p)
		DP[i][j] = best
		return best

	def longestIncreasingPath(self, matrix):
		best = 0
		n = len(matrix)
		m = len(matrix[0])
		DP = [[-1 for j in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				best = max(best, self.lip(matrix, i, j, n, m, DP))
		return best


class Solution:

	def longestIncreasingPath(self, l):
		(n, m, z) = (len(l), len(l[0]), 0)
		a = [[0] * m for i in range(n)]

		def path(r, c, p):
			if r < 0 or r == n or c < 0 or (c == m) or (l[r][c] <= p):
				return 0
			if a[r][c]:
				return a[r][c]
			(x, y) = (1, l[r][c])
			x += max(path(r, c - 1, y), path(r, c + 1, y), path(r - 1, c, y), path(r + 1, c, y))
			a[r][c] = x
			return x
		for i in range(n):
			for j in range(m):
				z = max(z, path(i, j, -1))
		return z


class Solution:

	def longestIncreasingPath(self, matrix):

		def sol(i, j, n, m):
			if dp[i][j] != -1:
				return dp[i][j]
			(w, x, y, z) = (0, 0, 0, 0)
			if i + 1 < n:
				if matrix[i + 1][j] - matrix[i][j] > 0:
					w = 1 + sol(i + 1, j, n, m)
			if j - 1 >= 0:
				if matrix[i][j - 1] - matrix[i][j] > 0:
					x = 1 + sol(i, j - 1, n, m)
			if i - 1 >= 0:
				if matrix[i - 1][j] - matrix[i][j] > 0:
					y = 1 + sol(i - 1, j, n, m)
			if j + 1 < m:
				if matrix[i][j + 1] - matrix[i][j] > 0:
					z = 1 + sol(i, j + 1, n, m)
			dp[i][j] = max(w, x, y, z, 1)
			return dp[i][j]
		n = len(matrix)
		m = len(matrix[0])
		mx = 1
		dp = [[-1 for i in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				mx = max(sol(i, j, n, m), mx)
		return mx


def LCP(matrix, i, j, dp):
	if i >= n or j >= m:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	ans1 = 0
	if i - 1 >= 0 and matrix[i - 1][j] > matrix[i][j]:
		ans1 = LCP(matrix, i - 1, j, dp)
	ans2 = 0
	if j - 1 >= 0 and matrix[i][j - 1] > matrix[i][j]:
		ans2 = LCP(matrix, i, j - 1, dp)
	ans3 = 0
	if i + 1 < n and matrix[i + 1][j] > matrix[i][j]:
		ans3 = LCP(matrix, i + 1, j, dp)
	ans4 = 0
	if j + 1 < m and matrix[i][j + 1] > matrix[i][j]:
		ans4 = LCP(matrix, i, j + 1, dp)
	dp[i][j] = 1 + max(ans1, ans2, ans3, ans4)
	return dp[i][j]

class Solution:

	def longestIncreasingPath(self, matrix):
		global n, m
		n = len(matrix)
		m = len(matrix[0])
		dp = [[-1 for i in range(m + 1)] for j in range(n + 1)]
		ans = 0
		for i in range(n):
			for j in range(m):
				ans = max(ans, LCP(matrix, i, j, dp))
		return ans


from collections import deque

class Solution:

	def longestIncreasingPath(self, matrix):
		dp = {}
		paths = [[0, 1], [1, 0], [-1, 0], [0, -1]]

		def dfs(i, j, prev):
			if i < 0 or j < 0 or i >= len(matrix) or (j >= len(matrix[0])) or (matrix[i][j] <= prev):
				return 0
			if (i, j) in dp:
				return dp[i, j]
			res = 1
			for path in paths:
				res = max(res, 1 + dfs(i + path[0], j + path[1], matrix[i][j]))
			dp[i, j] = res
			return res
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if (i, j) in dp:
					continue
				dfs(i, j, 0)
		ans = 0
		for (key, val) in dp.items():
			ans = max(ans, val)
		return ans


class Solution:

	def longestIncreasingPath(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		a = []
		for i in range(n):
			a.append([0] * m)

		def path(i, j):
			if a[i][j] != 0:
				return a[i][j]
			l = [[0, 1], [1, 0], [-1, 0], [0, -1]]
			for k in l:
				r = k[0] + i
				c = k[1] + j
				if r >= 0 and c >= 0 and (r < n) and (c < m) and (matrix[r][c] > matrix[i][j]):
					a[i][j] = max(path(r, c), a[i][j])
			a[i][j] += 1
			return a[i][j]
		ans = 1
		for i in range(n):
			for j in range(m):
				ans = max(ans, path(i, j))
		return ans


def findLongestFromACell(i, j, mat, dp, n, m):
	if i < 0 or i >= n or j < 0 or (j >= m):
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	(x, y, z, w) = (-1, -1, -1, -1)
	if j < m - 1 and mat[i][j] < mat[i][j + 1]:
		x = 1 + findLongestFromACell(i, j + 1, mat, dp, n, m)
	if j > 0 and mat[i][j] < mat[i][j - 1]:
		y = 1 + findLongestFromACell(i, j - 1, mat, dp, n, m)
	if i > 0 and mat[i][j] < mat[i - 1][j]:
		z = 1 + findLongestFromACell(i - 1, j, mat, dp, n, m)
	if i < n - 1 and mat[i][j] < mat[i + 1][j]:
		w = 1 + findLongestFromACell(i + 1, j, mat, dp, n, m)
	dp[i][j] = max(x, max(y, max(z, max(w, 1))))
	return dp[i][j]

class Solution:

	def longestIncreasingPath(self, matrix):
		result = 1
		n = len(matrix)
		m = len(matrix[0])
		dp = [[-1 for i in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				if dp[i][j] == -1:
					findLongestFromACell(i, j, matrix, dp, n, m)
				result = max(result, dp[i][j])
		return result


class Solution:

	def longestIncreasingPath(self, matrix):
		dp = {}
		mat = matrix
		(n, m) = (len(mat), len(mat[0]))

		def dfs(i, j):
			if (i, j) in dp:
				return dp[i, j]
			for (x, y) in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
				if 0 <= x + i < n and 0 <= y + j < m and (mat[i][j] < mat[x + i][y + j]):
					dp[i, j] = max(dp.get((i, j), 0), dfs(x + i, y + j))
			dp[i, j] = dp.get((i, j), 0) + 1
			return dp[i, j]
		ans = 0
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				ans = max(ans, dfs(i, j))
		return ans