Genome

Time limit2sMemory limit512 MB

Summary

Find the length of the longest sequence that appears as a subsequence in every given permutation.

Level: Medium6 of 10
Topics: Graph, Dynamic programming
Solved: No attempts yet

Problem

In comparative genomics, biologists want to find a gene sequence that is conserved across a group of species.

Let $\{1, 2, \ldots, n\}$ be a set of $n$ integers where each integer is one gene. There are $m$ species $S_1, S_2, \ldots, S_m$ , and each species $S_i$ is given as a permutation of $\{1, 2, \ldots, n\}$ . That permutation is the order of the genes in $S_i$ .

A subsequence of an integer sequence is obtained by omitting none, one, or more integers from the original sequence. An integer sequence $x_1, x_2, \ldots, x_k$ is a conserved gene sequence of the $m$ species if it is a subsequence of $S_i$ for every $i = 1, 2, \ldots, m$ . Find the length of a longest conserved gene sequence of the $m$ species.

Input

The first line contains two integers $n$ and $m$ separated by a space ( $1 \le n \le 100$ , $1 \le m \le 10$ ).

Each of the next $m$ lines contains a permutation of $1, 2, \ldots, n$ , with a space between two adjacent integers.

Output

Print one integer, the length of a longest conserved gene sequence.

Hint

Consider these 3 species.

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

The four sequences

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

are all conserved gene sequences of the 3 species, but none of them is longest. A longest conserved gene sequence of the 3 species is 5, 3, 1.

Examples1

Example 1
Input
```
5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4
```
Expected output
```
3
```