항체 중쇄 군집화

생물학자들이 바이러스성 질병의 치료제를 찾고 있다. 여러 기원의 항체를 바이러스 항원에 시험해 본 뒤, 실험에서 가장 잘 작동한 항체 $n$개를 골랐다.

항체는 저마다 중쇄로 구분한다. 중쇄는 아미노산을 늘어놓은 서열이고, 아미노산 하나는 영어 대문자 하나로 적는다.

항체의 집합이 다음 두 조건 중 적어도 하나를 만족하면 유사 군집이다.

• 모든 중쇄의 $k$-접두사(앞쪽 $k$개의 아미노산)가 서로 같다.
• 모든 중쇄의 $k$-접미사(뒤쪽 $k$개의 아미노산)가 서로 같다.

항체 하나로만 이루어진 집합은 언제나 유사 군집이다.

이후 연구를 간단히 하려고 생물학자들은 항체 $n$개를 유사 군집으로 나누려 한다. 항체는 모두 정확히 한 군집에만 속해야 한다. 군집이 최소 몇 개 필요한지 구하라.

첫째 줄에 중쇄의 개수 $n$과 일치해야 하는 아미노산 서열의 길이 $k$가 주어진다 ($1 \le n \le 5000$, $1 \le k \le 550$).

다음 $n$개 줄에는 항체의 중쇄가 한 줄에 하나씩 주어진다. 아미노산은 모두 영어 대문자이고, 중쇄의 길이는 $k$ 이상 $550$ 이하이다.

항체 $n$개를 나누는 데 필요한 유사 군집 개수의 최솟값을 정수 하나로 출력한다.