게놈

비교유전체학에서 생물학자는 여러 종에 공통으로 보존된 유전자 서열을 찾으려고 한다.

$\{1, 2, \ldots, n\}$은 정수 $n$개로 이루어진 집합이고, 각 정수는 유전자 하나를 뜻한다. 종은 $m$개이고 각각을 $S_1, S_2, \ldots, S_m$이라고 하자. 종 $S_i$는 $\{1, 2, \ldots, n\}$의 순열 하나로 주어지며, 이 순열이 $S_i$에서 유전자가 놓인 순서다.

정수 수열의 부분 수열은 원래 수열에서 정수를 하나도 지우지 않거나 하나 이상 지워서 얻는다. 정수 수열 $x_1, x_2, \ldots, x_k$가 모든 $i = 1, 2, \ldots, m$에 대해 $S_i$의 부분 수열이면, 이 수열을 $m$개 종의 보존 유전자 서열이라고 부른다. $m$개 종의 보존 유전자 서열 중 가장 긴 것의 길이를 구하라.

첫째 줄에 정수 $n$과 $m$이 공백을 사이에 두고 주어진다. ($1 \le n \le 100$, $1 \le m \le 10$)

다음 $m$개 줄에는 각 줄마다 $1, 2, \ldots, n$의 순열이 주어지고, 인접한 두 정수는 공백으로 구분한다.

가장 긴 보존 유전자 서열의 길이를 정수 하나로 출력한다.

다음 3개 종을 생각해 보자.

• 5, 3, 4, 1, 2
• 2, 5, 4, 3, 1
• 5, 2, 3, 1, 4

아래 네 수열

• 5, 1
• 5, 3
• 5, 4
• 3, 1

은 모두 이 3개 종의 보존 유전자 서열이지만 가장 길지는 않다. 가장 긴 보존 유전자 서열은 5, 3, 1이다.