Genomes

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.

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.

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