Genome

문제

In comparative genomic, biologists would like to find a gene sequence that is conserved among a set of species.

Let {1, 2, . . . , n} be a set of n integers in which each integer represents a gene. For the m species S₁, S₂, · · ·, S_m, each species S_i is identified by a permutation of {1, 2, . . . , n}. The permutation represents the ordering of 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₁, x₂, . . . , x_k is a conserved gene sequence among the m species if x₁, x₂, . . . , x_k is a subsequence of S_i for all i = 1, 2, . . . , m. Our aim is to find the length of the longest conserved gene sequences for the m species.

입력

The input contains m + 1 lines. The first line contains two integers n and m separated by spaces, where 1 ≤ n ≤ 100 and 1 ≤ m ≤ 10. Each of the next m lines contains a permutation of 1, 2, . . . , n, with spaces between two adjacent integers.

출력

The output contains an integer that gives the length of the longest conserved gene sequences.

힌트

Consider the following 3 species,

• 5, 3, 4, 1, 2;
• 2, 5, 4, 3, 1;
• 5, 2, 3, 1, 4.

The following subsequences

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

are conserved gene sequences among the 3 species but are not longest. The longest conserved gene sequence of the 3 species is 5, 3, 1.

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

3