게놈

시간 제한1초메모리 제한128 MB

요약

최대 500개의 유전자로 이루어진 최대 20개의 순열에 공통된 가장 긴 부분 수열의 길이를 구합니다.

난이도: 보통10점 중 6점
유형: 그래프, 위상 정렬, 동적 계획법
정답자: 아직 제출이 없습니다

문제

비교유전학을 연구하는 생물학자들이 여러 종에 걸쳐 보존된 유전자 서열을 찾고 있습니다.

집합 $\{1, 2, \dots, n\}$ 의 각 수가 하나의 유전자를 나타낸다고 합시다. 각 종은 자신의 유전자 배열 순서를 나타내는 $1, 2, \dots, n$ 의 순열 하나로 표현됩니다. 유전자 서열 $x_1, x_2, \dots, x_k$ 가 주어진 종들의 집합에서 보존된 유전자 서열이라는 것은, 이 서열이 각 종의 유전자 배열 순서의 (반드시 연속일 필요는 없는) 부분 수열이라는 뜻입니다.

표준 입력으로 유전자 배열들의 정보를 읽어들여, 가장 긴 보존된 서열의 길이를 구한 뒤 표준 출력으로 출력하는 프로그램을 작성하세요.

입력

첫째 줄에는 공백 하나로 구분된 두 정수 $n$ 과 $m$ 이 주어지며, $1 \le n \le 500$ , $1 \le m \le 20$ 입니다. $n$ 은 유전자의 수이고 $m$ 은 종의 수입니다. 이어지는 $m$ 개의 줄에는 각 종의 게놈이 한 줄에 하나씩, $1, 2, \dots, n$ 의 순열을 공백으로 구분하여 주어집니다.

출력

가장 긴 보존된 유전자 서열의 길이를 나타내는 정수 하나를 출력합니다.

예제4

예제 1
입력
```
5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4
```
예상 출력
```
3
```
예제 2
입력
```
1 1
1
```
예상 출력
```
1
```

예제 3

입력

예상 출력

예제 4
입력
```
5 1
3 1 2 5 4
```
예상 출력
```
5
```