Ибрагим заканчивает учебу в этом году и исследует самую длинную общую подпоследовательность для небольшой части своей диссертации. В своем исследовании ему нужно было найти самую длинную общую подпоследовательность перестановок. Ибрагим не хорош в перестановках. Помогите ему в этом.
Вам задано количество перестановок . Каждая перестановка — это последовательность чисел в произвольном порядке. Найдите длину самой длинной общей подпоследовательности заданных перестановок.
Примечание 1. Последовательность чисел , записанная в произвольном порядке, называется перестановкой из элементов.
Примечание 2. Подпоследовательность последовательности — это последовательность, которую можно получить из заданной последовательности удалением некоторых элементов без изменения порядка остальных элементов или не удаляя ни один из элементов. Подпоследовательность, входящая в две или более последовательностей,называется общей подпоследовательностью этих последовательностей.
В первой строке даны два целых числа и . В каждой из следующих строк задана перестановка, состоящая из целых чисел .
Выведите длину самой длинной общей подпоследовательности заданных перестановок.
В первом примере последовательность или является самой длинной общей подпоследовательностью. Они обе встречаются в обеих перестановках.
Во втором примере — самая длинная общая подпоследовательность. Она встречается во всех трёх перестановках.