eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Юрский пазл

Юрский пазл

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Знаменитый биолог парка юрского периода Дин О'Саур обнаружил новые образцы того, что он ожидает от ДНК динозавра. С помощью своего помощника Петры Дактил ему удалось упорядочить образцы, и теперь они готовы к анализу. Дин считает, что этот динозавр был поражен определенным заболеванием, мутировавшим ДНК некоторых клеток.

Чтобы проверить свою теорию, он должен вычислить наиболее вероятное эволюционное дерево из образцов, где узлами являются образцы ДНК. Поскольку нет временных данных образцов ДНК, его не волнует, где находится корень дерева.

Дин рассматривает наиболее вероятное эволюционное дерево - дерево с наименьшей вероятностью: вероятность дерева определяется как сумма весов всех ребер, где вес ребра - это число позиций, в которых две строки ДНК различны.

Будучи мировым экспертом по деревьям данных, он просит Вас реконструировать наиболее вероятное эволюционное дерево.

В первом примере оптимальным деревом будет AA - AT - TT - TC. Неправдоподобие ребра между AA и AT равно 1, так как строки AA и AT разнятся в 1 позиции. Веса других двух ребер равны 1. Поэтому вероятность всего дерева равна 3. Поскольку не существует дерева с вероятностью меньше 3, то минимальная вероятность эволюционного дерева для этого теста составляет 3.

Входные данные

Первая строка содержит два целых числа n (1n1000) и k (1k10) - количество образцов и их длина. Каждая из следующих n строк содержит строку длины k состоящую из символов ACTG.

Выходные данные

В первой строке выведите наименьшее значение вероятности эволюционного дерева. Далее выведите n1 строку, каждая из которых содержит два целых числа u, v (0u, v < n), указывающих что в эволюционном дереве скорее всего будет присутствовать ребро между ДНК строками u и v. Если существует несколько решений, выведите любое.

Пример

Входные данные #1
4 2
AA
AT
TT
TC
Выходные данные #1
3
0 1
1 2
2 3
Входные данные #2
4 1
A
A
G
T
Выходные данные #2
2
0 1
0 2
0 3
Входные данные #3
5 6
GAACAG
AAAAAA
AACATA
GAAAAG
ATAAAT
Выходные данные #3
7
0 3
1 2
1 3
1 4
Источник 2018 Benelux Algorithm Programming Contest (BAPC), Preliminaries, Задача J