Genomes

Time limit1sMemory limit128 MB

Summary

Find the length of the longest common subsequence of up to 20 permutations of size up to 500.

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

Problem

Biologists working in comparative genetics are looking for gene sequences that are conserved across a set of species.

Let the set $\{1, 2, \dots, n\}$ denote the genes, so that each number corresponds to one gene. Every species is described by a permutation of $1, 2, \dots, n$ that gives the ordering of its genes. A gene sequence $x_1, x_2, \dots, x_k$ is a conserved gene sequence for a set of species if it is a subsequence (not necessarily contiguous) of the gene ordering of every one of those species.

Write a program that reads the gene orderings from standard input, determines the length of the longest conserved sequence, and writes that length to standard output.

Input

The first line contains two integers $n$ and $m$ separated by a single space, with $1 \le n \le 500$ and $1 \le m \le 20$ . Here $n$ is the number of genes and $m$ is the number of species. Each of the next $m$ lines contains the genome of one species, written as a permutation of $1, 2, \dots, n$ with the numbers separated by single spaces.

Output

Print a single integer equal to the length of the longest conserved gene sequence.

Examples4

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

Example 3

Input

Expected output

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