8502번 - Genomy 다국어

Biolodzy zajmujący się genetyką porównawczą poszukują sekwencji genów zachowanych w pewnym zbiorze gatunków.

Niech zbiór liczb {1,2,…,n} oznacza geny - każdej liczbie odpowiada jeden gen. Każdy z gatunków określony jest permutacją liczb (1,2,…,n}, która oznacza uporządkowanie jego genów. Ciąg genów x₁,x₂,…,x_k jest zachowaną sekwencją genów w zbiorze gatunków, jeśli jest on podciągiem (niekoniecznie spójnym) uporządkowania genów każdego z tych gatunków.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis sekwencji genów,
• wyznaczy długość najdłuższej zachowanej sekwencji,
• zapisze odpowiedź na standardowe wyjście.

W pierwszej linii standardowego wejścia znajdują się dwie liczby całkowite n i m oddzielone pojedynczym odstępem, przy czym 1 ≤ n ≤ 500 oraz 1 ≤ m ≤ 20. Liczba n oznacza liczbę genów, a m liczbę gatunków. Każda z następnych m linii zawiera genom kolejnego gatunku zapisany jako permutacja liczb 1,2,…,n pooddzielanych pojedynczymi odstępami.

Na wyjściu powinna zostać wypisana dokładnie jedna liczba całkowita równa długości najdłuższej zachowanej sekwencji genów.