Пазл Юрського періоду
Знаменитий біолог Парку Юрського періоду Дін О'Саур виявив нові зразки того, що, на його думку, є ДНК динозавра. За допомогою свого помічника Петра Дактіла йому вдалося впорядкувати зразки, і тепер вони готові до аналізу. Дін вважає, що цей динозавр був уражений певним захворюванням, яке мутувало ДНК деяких клітин.
Щоб перевірити свою теорію, він повинен визначити найімовірніше еволюційне дерево із зразків, де вузлами є зразки ДНК. Оскільки немає часових даних зразків ДНК, його не хвилює де знаходиться корінь дерева.
Дін вважає найімовірнішим еволюційним деревом — дерево з найменшою несхожістю: несхожість дерева визначається як сума ваг усіх ребер, де вага ребра — це число позицій, в яких два рядки ДНК відрізняються.
Як світовий експерт із дерев даних, він просить Вас реконструювати найімовірніше еволюційне дерево.
У першому прикладі оптимальним деревом буде AA - AT - TT - TC. Несхожість ребра між AA і AT дорівнює 1, тому що рядки AA та AT відрізняються рівно 1 позицією. Ваги інших двох ребер також дорівнюють 1. Тому несхожість всього дерева дорівнює 3. Оскільки не існує дерева з несхожістю менше за 3, мінімальна несхожість еволюційного дерева для цього тесту становить 3.
Вхідні дані
Перший рядок містить два цілих числа n (1 ≤ n ≤ 1000) та k (1 ≤ k ≤ 10) — кількість зразків та їх довжина. Кожен із наступних n рядків містить рядок довжини k що складається із символів ACTG.
Вихідні дані
У першому рядку виведіть мінімальну несхожість еволюційного дерева. Далі виведіть n − 1 рядок, кожен з яких містить два цілих числа u, v (0 ≤ u, v < n), які вказують, що в найімовірнішому еволюційному дереві буде присутнє ребро між рядками ДНК u та v. Якщо існує кілька розв`язків, виведіть будь-який.