Ключи
Адам носит связку ключей, прикрепленных к кольцам, некоторые из которых могут быть соединены друг с другом. Кольца — это обычные кольца для ключей, поэтому ключ можно прикрепить или отсоединить от кольца, скользя по спирали. Таким же образом два кольца могут быть соединены или разъединены. Адам хочет отдать часть ключей Бренде. Поскольку манипуляции с ключами и кольцами часто являются утомительным занятием (и также опасным для ногтей), Адам ищет способ минимизировать количество операций с ключами и кольцами.
Каждое прикрепление ключа, отсоединение ключа, соединение кольца или разъединение кольца считается одной операцией. Поскольку манипуляции с двумя кольцами значительно проще, чем скольжение ключа, мы сначала хотим минимизировать количество отсоединяемых и прикрепляемых ключей. Среди решений с одинаковым минимальным количеством операций с ключами, необходимо найти то, которое имеет минимальное количество соединений и разъединений колец.
Когда все операции завершены, Адам и Бренда должны каждый носить одну связанную группу колец и ключей. Единственное исключение — когда у кого-то из них вообще не будет ключей — в таком случае кольцо не нужно. Каждый ключ должен быть прикреплен к точно одному кольцу. Некоторые кольца (но не ключи) могут считаться остатками и могут оставаться отключенными от двух групп.
Левая сторона следующей фигуры показывает начальную конфигурацию, состоящую из четырех ключей на трех кольцах. Адам хочет отдать Бренде два ключа, обозначенные N и R. Это можно сделать двумя операциями с ключами и одной операцией с кольцом, что приводит к конфигурации, показанной на правой стороне фигуры.
Входные данные
Каждый тестовый случай содержит одну или несколько строк, каждая из которых содержит строку из двух букв. Строчные буквы (a - z) представляют кольца для ключей, а заглавные буквы (A - Z) представляют ключи. Две буквы в строке указывают либо на ключ, прикрепленный к кольцу, либо на два соединенных кольца. Конец каждого тестового случая обозначается строкой, содержащей цифру ноль.
Ключи, обозначенные буквами A до M, остаются у Адама, а ключи, обозначенные буквами N до Z, передаются Бренде.
Ни одна строка не содержит две заглавные буквы. Ни одна пара букв не указывается более одного раза в одном тестовом случае. Каждый ключ соединен ровно с одним кольцом. В конфигурациях колец нет "кругов" (разъединение любых двух колец увеличит количество связанных групп). Все существующие ключи и кольца упоминаются хотя бы один раз.
Выходные данные
Для каждого тестового случая выведите номер случая, за которым следует минимальное количество операций прикрепления/отсоединения ключей и минимальное количество операций соединения/разъединения колец.
Если нет способа разделить ключи, как требуется, выведите номер случая и слово impossible вместо двух чисел.