Informática Avançado - Semana 46

Maior Ancestral Comum

Há muitos anos, cientistas usam da genética para estudar a evolução das espécies. Dr. Mustavo está estudando uma nova teoria evolutiva. Nela, a evolução ocorre quando um novo gene é inserido no DNA de uma espécie. Deste modo, a sequência genética (1,3,7,5) é uma evolução da sequência (1,3,5), qm que o 7 foi o gene inserido entre os genes 3 e 5. Ainda mais, (2,1,3,7,5) e uma evolução de (1,3,7,5).

Para testar sua teoria, Dr. Mustavo precisa analisar ancestrais comuns entre duas espécies distintas. Para isso, ele precisa descobrir qual a maior sequência genética que pode representar o DNA de um ancestral comum a duas espécies e analisar o grau de semelhança entre o ancestral e os descendentes. Ao analisar, por exemplo, as espécies (1, 7, 2, 5, 2) e (3, 7, 1, 5, 2, 2) a maior sequência genética possivel para um ancestral comum das duas tem tamanho 3, podendo ser (1,2,2) ou (1,5,2), por exemplo. No caso (1,2,2), este pode ser ancestral da primeira sequência através da seguinte ordem evolutiva: (1,2,2), (1,7,2,2), (1,7,2,5,2), e da segunda através da ordem (1,2,2), (3,1,2,2), (3,7,1,2,2), (3,7,1,2,5,2).

O que realmente interessa a Mustavo é a distância entre as espécies e seus ancestrais. Essa distância é medida pelo númerod e evoluções que a espécie teve que fazer para chegar em uma determinada outra. Note, por exemplo, que a distância de (1,2,2) para (3, 7, 1, 5, 2, 2) são 3 evoluções. Dadas duas seuências de DNA, diga a distâcia de cada uma delas para o maior ancestral comum possível das duas. Note que se duas sequências não têm ancestral comum, as distâncias sao seus próprios tamanhos, pois consideraremos a sequência vazia como o ancestral.

Entrada

A primeira linha da entrada tem dois inteiros n e m (1\leq n,m\leq 1000)$, o tamanho de cada uma das duas sequências. A segunda linha contêm n inteiros: os genes da primeira sequência genética e a terceira contêm outros m inteiros: os genes da segunda sequência. Cada gene é um número entre 0 e 100, inclusive.

Saída

Seu programa deve imprimir dois inteiros: as distâncias genéticas da primeira e da segunda sequencia para o ancestral comum delas, respectivamente.

Exemplos

ENTRADA SAÍDA
5 6
1 7 2 5 2
3 7 1 5 2 2
2 3
3 4
1 1 1
2 2 2 2
3 4
4 4
1 1 2 1
1 2 1 1
1 1