У Фермера Джона NN коров с пятнами и NN коров без пятен. Пройдя курс генетики, ФД убеждён, что пятна у коров вызваны мутацией генов.
За большие деньги ФД зафиксировал геномы своих коров. Каждый геном это строка длиной MM, состоящая из символов A, C, G, T. Когда он выписал все геномы у него получилась такая таблица, N=3 и M=8:
Позиция : 1 2 3 4 5 6 7 8
Пятнистая корова 1: A A T C C C A T
Пятнистая корова 2: A C T T G C A A
Пятнистая корова 3: G G T C G C A A
Корова без пятен 1: A C T C C C A G
Корова без пятен 2: A C T C G C A T
Корова без пятен 3: A C T T C C A T
Посмотрев внимательно на эту таблицу, он заметил, что последовательность от позиции 2 до позиции 5 успешна, чтобы объяснять пятнистость. То есть, рассматривая символы в этих позициях (2…5), ФД может предсказать какие из его коров пятнистые, а какие нет. Например, если он видит символы GTCG в этих позициях, он знает, что корова будет пятнистая.
Помогите ФД определить длину кратчайшей последовательности позиций, которая может объяснить пятнистость.
ФОРМАТ ВВОДА:
Первая строка ввода содержит N (1≤N≤500) и M (3≤M≤500). Каждая из N следующих строк содержит по M символов. Эти символы описывают геномы пятнистых коров. Следующие N строк описывают геномы коров без пятен. Никакая пятнистая корова на имеет точно такой же геном, как корова без пятен.
ФОРМАТ ВЫВОДА:
Пожалуйста, выведите длину кратчайшей последовательности позиций, достаточной для объяснения пятнистости. Последовательность позиций объясняет пятнистость, если по ней можно предсказывать абсолютно точно пятнистая или нет любая из коров ФД.
| Ввод |
Вывод |
|
3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT
|
4 |