쥐라기 직소

시간 제한1초메모리 제한512 MB

요약

길이 k인 DNA 문자열 n개가 주어질 때, 간선의 해밍 거리 합이 최소인 신장 트리를 만들어 그 비용과 간선 목록을 출력한다.

난이도: 보통10점 중 6점
유형: 최소 신장 트리, 그래프, 그리디, 문자열
정답자: 아직 제출이 없습니다

문제

저명한 쥐라기 공원 생물학자 Dean O’Saur는 공룡의 DNA라고 생각되는 새로운 샘플을 발견했다. 조수 Petra Dactil의 도움으로 샘플의 염기 서열을 밝혀냈고, 이제 분석할 준비가 되었다. Dean은 이 공룡이 일부 세포의 DNA를 변이시키는 특정 질병에 걸렸다고 생각한다.

그의 가설을 검증하려면 샘플들로부터 가장 그럴듯한 진화 트리를 계산해야 한다. 트리의 노드는 DNA 샘플이다. DNA 샘플의 시간 정보가 없으므로 트리의 루트가 어디인지는 신경 쓰지 않는다.

Dean은 가장 그럴듯한 진화 트리를 최소 비유사도를 갖는 트리로 본다. 트리의 비유사도는 모든 간선의 가중치 합으로 정의하고, 간선의 가중치는 두 DNA 문자열이 다른 위치의 개수이다.

데이터 트리의 세계적 전문가인 그가 당신에게 가장 그럴듯한 진화 트리를 복원해 달라고 부탁한다.

첫 번째 예시에서 최적 트리는 AA - AT - TT - TC이다. AA와 AT를 잇는 간선의 비유사도는 1이다. 두 문자열 AA와 AT가 정확히 1개 위치에서 다르기 때문이다. 나머지 두 간선의 가중치도 1이므로 트리 전체의 비유사도는 3이다. 비유사도가 3보다 작은 트리는 없으므로 이 경우 진화 트리의 최소 비유사도는 3이다.

입력

첫째 줄에 두 정수 1 ≤ n ≤ 1000과 1 ≤ k ≤ 10이 주어진다. 각각 샘플의 개수와 각 샘플의 길이이다.
다음 n개 줄에 ACTG 문자로 이루어진 길이 k의 문자열이 하나씩 주어진다.

출력

첫째 줄에 진화 트리의 최소 비유사도를 출력한다.
다음 n − 1개 줄에 두 정수 0 ≤ u, v < n을 출력한다. 가장 그럴듯한 진화 트리에서 DNA 문자열 u와 v 사이에 간선이 있음을 뜻한다. 가능한 답이 여러 개면 아무거나 출력해도 된다.

예제3

예제 1
입력
```
4 2
AA
AT
TT
TC
```
예상 출력
```
3
0 1
1 2
2 3
```
예제 2
입력
```
4 1
A
A
G
T
```
예상 출력
```
2
0 1
0 2
0 3
```

예제 3

입력

5 6
GAACAG
AAAAAA
AACATA
GAAAAG
ATAAAT

예상 출력