Ibrahim's dissertation#11669
Ibrahim is finishing his studies this year and is exploring the longest common subsequence for a small part of his dissertation. In his research, he needed to find the longest common subsequence of permutations. Ibrahim is not good at permutations. Help him with this.
You are given the number of permutations . Each permutation is a sequence of numbers 1, 2, ..., n in arbitrary order. Find the length of the longest common subsequence of the given permutations.
The first line contains two integers n~(1 \le n \le 1000) and k~(2 \le k \le 5). Each of the next lines contains a permutation consisting of integers 1, 2, ..., n.
Print the length of the longest common subsequence of the given permutations.
In the first example, the sequence or is the longest common subsequence. They both appear in both permutations.
In the second example, is the longest common subsequence. It appears in all three permutations.
Example 1
Example 2
Note 1. A sequence of numbers 1, 2, ..., n written in arbitrary order is called a permutation of elements.
Note 2. A subsequence of a sequence is a sequence that can be obtained from the given sequence by removing some elements without changing the order of the remaining elements or without removing any elements. A subsequence that belongs to two or more sequences is called a common subsequence of these sequences.