Gargari got bored to play with the bishops and now, after solving the problem about them, he is trying to do math homework. In a math book he have found k permutations. Each of them consists of numbers 1, 2, ..., n in some order. Now he should find the length of the longest common subsequence of these permutations. Can you help Gargari?

You can read about longest common subsequence there: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 1000; 2 ≤ k ≤ 5). Each of the next k lines contains integers 1, 2, ..., n in some order — description of the current permutation.


-----Output-----

Print the length of the longest common subsequence.


-----Examples-----
Input
4 3
1 4 2 3
4 1 2 3
1 2 4 3

Output
3



-----Note-----

The answer for the first test sample is subsequence [1, 2, 3].

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Graph algorithms

Graph traversal

Implementation


Solutions:
import os
import sys
from io import BytesIO, IOBase

def main():
	(n, k) = map(int, input().split())
	a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(k)]
	b = [[0] * n for _ in range(k)]
	for i in range(k):
		for j in range(n):
			b[i][a[i][j]] = j
	dp = [[0] * n for _ in range(k)]
	for i in range(n - 1, -1, -1):
		for j in range(k):
			(maa, ele) = (0, a[j][i])
			for m in range(k):
				if b[m][ele] < i:
					break
			else:
				for l in range(b[j][ele] + 1, n):
					ma = 0
					for m in range(k):
						if b[m][ele] > b[m][a[j][l]]:
							break
						ma = max(ma, dp[m][b[m][a[j][l]]])
					else:
						maa = max(maa, ma)
				dp[j][i] = maa + 1
	print(max((max(i) for i in dp)))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(k)]
g = [[] for i in range(n + 1)]
for i in range(n):
	x = a[0][i]
	s = set(a[0][i + 1:])
	for j in range(k):
		idx = a[j].index(x)
		s1 = set(a[j][idx + 1:])
		s = s & s1
	for y in s:
		g[x].append(y)
dist = [-1] * (n + 1)

def dfs(ver):
	if dist[ver] != -1:
		return dist[ver]
	res = 0
	for to in g[ver]:
		res = max(res, dfs(to) + 1)
	dist[ver] = res
	return res
MAX = max((dfs(i) for i in range(1, n + 1)))
print(MAX + 1)


(n, k) = list(map(int, input().split()))
(a, b) = ([[] for row in range(6)], [[0 for col in range(n + 1)] for row in range(6)])
for i in range(k):
	a[i] = list(map(int, input().split()))
	for j in range(n):
		b[i][a[i][j]] = j
dp = [1] * n
for i in range(n):
	for j in range(i):
		flag = 1
		for x in range(1, k):
			if b[x][a[0][j]] > b[x][a[0][i]]:
				flag = 0
				break
		if flag:
			dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))


from sys import stdin, stdout, setrecursionlimit
input = stdin.readline
inf = float('inf')
from functools import cmp_to_key
from collections import defaultdict as dd
from collections import Counter, deque
from heapq import *
import math
from math import floor, ceil, sqrt

def geti():
	return map(int, input().strip().split())

def getl():
	return list(map(int, input().strip().split()))

def getis():
	return map(str, input().strip().split())

def getls():
	return list(map(str, input().strip().split()))

def gets():
	return input().strip()

def geta():
	return int(input())

def print_s(s):
	stdout.write(s + '\n')

def solve():
	(n, k) = geti()
	mat = []
	pos = [[-1] * (n + 1) for _ in range(k)]
	for i in range(k):
		mat.append(getl())
		for j in range(n):
			pos[i][mat[-1][j]] = j
	dp = [1] * n
	for i in range(n):
		for j in range(i):
			for now in range(k):
				if pos[now][mat[0][i]] <= pos[now][mat[0][j]]:
					break
			else:
				dp[i] = max(dp[i], dp[j] + 1)
	ans = max(dp)
	print(ans)
solve()


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(N, K, A, pos):
	dp = [0 for _ in range(N + 1)]
	for i in range(1, N + 1):
		maxx = 0
		for p in range(1, i):
			if all([pos[k][A[1][p]] < pos[k][A[1][i]] for k in range(2, K + 1)]):
				maxx = max(maxx, dp[p])
		dp[i] = maxx + 1
	return max(dp)
(N, K) = map(int, input().split())
A = [[0] * (N + 1)]
pos = [[0 for _ in range(N + 1)] for _ in range(K + 1)]
for i in range(K):
	row = [0] + [int(x) for x in input().split()]
	A.append(row)
	for (j, v) in enumerate(row):
		pos[i + 1][v] = j
print(solve(N, K, A, pos))


(n, k) = list(map(int, input().split()))
ra = [[0] * k for _ in range(n)]
for p in range(k):
	for (i, v) in enumerate(map(int, input().split())):
		v -= 1
		ra[v][p] = i
g = [[] for _ in range(n)]
for u in range(n):
	for v in range(n):
		if all((x < y for (x, y) in zip(ra[u], ra[v]))):
			g[u].append(v)
memo = [-1] * n

def dfs(v):
	if memo[v] != -1:
		return memo[v]
	r = 1
	for u in g[v]:
		r = max(r, dfs(u) + 1)
	memo[v] = r
	return r
print(max((dfs(s) for s in range(n))))


import os, sys
from io import BytesIO, IOBase

def main():
	(n, k) = map(int, input().split())
	arr = [list(map(int, input().split())) for _ in range(k)]
	edg = [[1] * n for _ in range(n)]
	for i in range(k):
		for j in range(n):
			for l in range(j + 1):
				edg[arr[i][j] - 1][arr[i][l] - 1] = 0
	path = [[] for _ in range(n)]
	for i in range(n):
		for j in range(n):
			if edg[i][j]:
				path[i].append(j)
	(visi, poi, dp) = ([0] * n, [0] * n, [1] * n)
	for i in range(n):
		if visi[i]:
			continue
		(visi[i], st) = (1, [i])
		while len(st):
			(x, y) = (st[-1], path[st[-1]])
			while poi[x] != len(y) and visi[y[poi[x]]]:
				dp[x] = max(dp[x], dp[y[poi[x]]] + 1)
				poi[x] += 1
			if poi[x] == len(y):
				st.pop()
				if len(st):
					dp[st[-1]] = max(dp[st[-1]], dp[x] + 1)
			else:
				st.append(y[poi[x]])
				visi[st[-1]] = 1
				poi[x] += 1
	print(max(dp))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def solve():
	(n, k) = map(int, input().split())
	c = [[-1 for i in range(n + 1)] for i in range(k)]
	dp = [0 for i in range(n + 1)]
	a = []
	for i in range(k):
		b = list(map(int, input().split()))
		for (j, v) in enumerate(b):
			c[i][v] = j
		a.append(b)
	for i in range(n):
		curpos = a[0][i]
		dp[i] = 1
		for j in range(i):
			prevpos = a[0][j]
			ok = True
			for p in range(k):
				if c[p][curpos] < c[p][prevpos]:
					ok = False
					break
			if ok:
				dp[i] = max(dp[i], dp[j] + 1)
	print(max(dp))
	return

def main():
	t = 1
	for _ in range(t):
		solve()
main()


import os
import sys
from io import BytesIO, IOBase

def main():
	(n, k) = map(int, input().split())
	arr = []
	for _ in range(k):
		arr.append(list(map(int, input().split())))
	indexes = [[0 for _ in range(n)] for _ in range(k)]
	for r in range(1, k):
		for i in range(n):
			indexes[r][arr[r][i] - 1] = i
	graph = [[] for _ in range(n + 1)]
	arr = arr[0]
	for i in range(n):
		for j in range(i + 1, n):
			(x, y) = (arr[i], arr[j])
			flag = 1
			for z in range(1, k):
				if indexes[z][x - 1] < indexes[z][y - 1]:
					pass
				else:
					flag = 0
					break
			if flag:
				graph[x].append(y)
	depth = [0] * (n + 1)
	vis = [0] * (n + 1)
	idx = [0] * (n + 1)
	for i in range(1, n + 1):
		if vis[i]:
			continue
		vis[i] = 1
		stack = [i]
		while stack:
			x = stack[-1]
			y = idx[x]
			if y == len(graph[x]):
				stack.pop()
				if stack:
					depth[stack[-1]] = max(depth[stack[-1]], depth[x] + 1)
			else:
				z = graph[x][y]
				if vis[z]:
					depth[x] = max(depth[x], depth[z] + 1)
				else:
					stack.append(z)
					vis[stack[-1]] = 1
				idx[x] += 1
	print(max(depth) + 1)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def main():
	(n, k) = tuple(map(int, input().split()))
	a = [set(range(n)) for _ in range(n)]
	for i in range(k):
		p = set()
		for j in map(int, input().split()):
			a[j - 1] -= p
			p.add(j - 1)
	sa = sorted(list(range(n)), key=lambda i: len(a[i]))
	maxx = [0] * n
	res = 0
	for i in sa:
		m = 1 + maxx[max(a[i], key=lambda e: maxx[e])] if a[i] else 0
		maxx[i] = m
		res = max(res, m)
	print(res)

def __starting_point():
	main()
__starting_point()


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
(n, k) = map(int, input().split())
dp = [0 for i in range(n + 1)]
ans = 0
s = [[n for i in range(n + 1)] for j in range(k)]
l = []
for i in range(k):
	l.append(list(map(int, input().split())))
	s[i][0] = -1
	for j in range(n):
		s[i][l[i][j]] = j
for t in range(n):
	for j in range(n + 1):
		f = 0
		for i in range(k):
			if s[i][j] >= s[i][l[0][t]]:
				f = 1
				break
		if f == 0:
			dp[l[0][t]] = max(dp[l[0][t]], dp[j] + 1)
for i in range(n + 1):
	ans = max(ans, dp[i])
print(ans)


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List
memo = [0 for _ in range(1005)]

def longestpath(start, graph):
	if memo[start] > 0:
		return memo[start]
	l = 0
	for v in graph[start]:
		l = max(longestpath(v, graph), l)
	memo[start] = l + 1
	return l + 1

def solve_graph(N, K, A, pos):
	g = collections.defaultdict(list)
	d = [0 for _ in range(N + 1)]
	for u in range(1, N + 1):
		for v in range(1, N + 1):
			if all([pos[k][u] < pos[k][v] for k in range(1, K + 1)]):
				g[u].append(v)
				d[v] += 1
	ans = 0
	for u in range(1, N + 1):
		if d[u] == 0:
			ans = max(ans, longestpath(u, g))
	return ans

def solve(N, K, A, pos):
	dp = [0 for _ in range(N + 1)]
	for i in range(1, N + 1):
		maxx = 0
		for p in range(1, i):
			if all([pos[k][A[1][p]] < pos[k][A[1][i]] for k in range(2, K + 1)]):
				maxx = max(maxx, dp[p])
		dp[i] = maxx + 1
	return max(dp)
(N, K) = map(int, input().split())
A = [[0] * (N + 1)]
pos = [[0 for _ in range(N + 1)] for _ in range(K + 1)]
for i in range(K):
	row = [0] + [int(x) for x in input().split()]
	A.append(row)
	for (j, v) in enumerate(row):
		pos[i + 1][v] = j
print(solve_graph(N, K, A, pos))