소 유전체 분석 (Gold)

농부 존에게는 반점이 있는 소 $N$마리와 반점이 없는 소 $N$마리가 있다. 소 유전학 강의를 막 마친 존은 소의 반점이 소 유전체의 돌연변이 때문에 생긴다고 확신한다.

존은 큰 비용을 들여 소들의 유전체를 해독했다. 각 유전체는 A, C, G, T 네 문자로 이루어진 길이 $M$의 문자열이다. 소들의 유전체를 나란히 늘어놓으면 다음과 같은 표가 된다. 아래는 $N=3$, $M=8$인 경우이다.

Positions:    1 2 3 4 5 6 7 8

Spotty Cow 1: A A T C C C A T
Spotty Cow 2: A C T T G C A A
Spotty Cow 3: G G T C G C A A

Plain Cow 1:  A C T C C C A G
Plain Cow 2:  A C T C G C A T
Plain Cow 3:  A C T T C C A T

표를 자세히 살펴본 존은 위치 2부터 위치 5까지의 구간만으로 반점 여부를 설명할 수 있다고 추측한다. 즉 이 위치들(위치 $2 \ldots 5$)의 문자만 보고도 어느 소에게 반점이 있고 어느 소에게 없는지 알 수 있다. 예를 들어 이 위치에서 GTCG라는 문자열을 보면 그 소는 반드시 반점이 있는 소이다.

반점 여부를 설명할 수 있는 연속한 위치 구간 중 가장 짧은 구간의 길이를 구하라.

첫째 줄에 $N$ ($1 \leq N \leq 500$)과 $M$ ($3 \leq M \leq 500$)이 주어진다. 다음 $N$개의 줄에는 반점이 있는 소의 유전체가 한 줄에 하나씩 길이 $M$의 문자열로 주어진다. 마지막 $N$개의 줄에는 반점이 없는 소의 유전체가 같은 형식으로 주어진다. 반점이 있는 소와 반점이 없는 소의 유전체가 완전히 같은 경우는 없다.

반점 여부를 설명하기에 충분한 가장 짧은 연속 위치 구간의 길이를 출력한다. 유전체에서 어떤 구간의 위치만 보고도 존의 모든 소에 대해 반점 여부를 틀림없이 예측할 수 있으면 그 구간은 반점 여부를 설명한다고 한다.