Алгоритмы на графах

Лифт ожил! Привалов и Амперян согласились ехать на 76 этаж НИИ ЧАВО в город Тьмускорпионь. Но возникла проблема, которую надо срочно решить: упомянутым добровольцам, на всякий случай, нужны планы этажей, начиная с 76 и выше. У Привалова есть карманный компьютер, но необходимо максимально сэкономить его память для хранения этих карт.

Каждый этаж НИИ ЧАВО представляется прямоугольным полем n × m. В некоторых местах на этажах расположены важные элементы инфраструктуры. В соответствующих клетках поля должны располагаться буквы латинского алфавита. Одинаковыми буквами обозначены одинаковые элементы инфраструктуры, а разными – разные. При этом заглавные и строчные буквы различаются. На карманный компьютер Привалова необходимо отправить k планов этажей последовательно. Есть два способа передать план этажа:

Требуется написать программу, которая определит последовательность передачи планов этажей с наименьшими затратами памяти.

Формат входных данных

В первой строке указаны числа n, m, k, w (1 ≤ n, m ≤ 10, 1 ≤ k, w ≤ 1000). Далее следуют описания этажей. Каждый этаж описывается n строками по m символов в каждой. Каждый символ это либо буква латинского алфавита, либо символ точка («.»), означающий пустую клетку на плане этажа.

Формат выходных данных

В первой строке должно быть одно целое число, означающие минимальное количество байт необходимых для хранения планов всех этажей. В следующих k строках нужно вывести описания способа передачи последовательности этажей. Каждая из этих строк состоит из двух чисел ai и bi. Число ai означает номер этажа, в соответствии с порядком, определенным входными данными, план которого будет передаваться следующим. Число bi равно 0, если указанный план будет передаваться первым способом (т.е. полностью). Если план для этажа ai будет передаваться вторым способом, то число bi равно порядковому номеру этажа, относительно которого будет передано отличие.

• Если фамилия начинается с букв "А".."Л", то необходимо реализовать алгоритм Краскала.
• Если фамилия начинается с букв "М".."Я", то необходимо реализовать алгоритм Прима.

Примеры входных и выходных данных

Примеры прикреплены к заданию.