Ключі
Адам має зв'язку ключів, прикріплених до кільця для ключів, деякі з яких можуть бути з'єднані між собою. Кільця є звичайними кільцями для ключів, тому ключ можна прикріпити або від'єднати від кільця, просунувши його вздовж спіралі. Таким же чином два кільця можуть бути з'єднані або роз'єднані. Адам хоче передати деякі ключі Бренді. Оскільки маніпуляції з ключами та кільцями часто є дратівливим завданням (а також небезпечним для нігтів), Адам шукає спосіб мінімізувати кількість операцій з ключами та кільцями.
Кожне прикріплення ключа, від'єднання ключа, з'єднання кільця або роз'єднання кільця вважається однією операцією. Оскільки маніпуляції з двома кільцями значно легші, ніж просування ключа, ми спочатку хочемо мінімізувати кількість від'єднаних і прикріплених ключів. Серед рішень з однаковою мінімальною кількістю операцій з ключами, потрібно знайти те, яке має мінімальну кількість з'єднань і роз'єднань кілець.
Коли всі операції завершені, Адам і Бренда повинні мати по одній з'єднаній групі кілець і ключів. Єдиний виняток - коли хтось із них не має жодного ключа взагалі - в такому випадку кільце не потрібне. Кожен ключ має бути прикріплений до одного кільця. Деякі кільця (але не ключі) можуть вважатися залишками і можуть залишатися від'єднаними від двох груп.
Ліва сторона наступної фігури показує початкову конфігурацію, що складається з чотирьох ключів на трьох кільцях. Адам хоче віддати Бренді два ключі, позначені N та R. Це можна здійснити за допомогою двох операцій з ключами та однієї операції з кільцем, що призводить до конфігурації, показаної на правій стороні фігури.
Вхідні дані
Кожен тестовий випадок містить один або більше рядків, кожен з яких містить дволітерний рядок. Маленькі літери (a - z) представляють кільця для ключів, а великі літери (A - Z) представляють ключі. Дві літери в рядку вказують або на ключ, прикріплений до кільця, або на два з'єднані кільця. Кінець кожного тестового випадку позначається рядком, що містить цифру нуль.
Ключі, позначені літерами A до M, залишаються у Адама, а ключі, позначені літерами N до Z, віддаються Бренді.
Жоден рядок не містить двох великих літер. Жодна пара літер не вказується більше одного разу в одному тестовому випадку. Кожен ключ з'єднаний з одним кільцем. У конфігураціях кілець немає "кіл" (роз'єднання будь-яких двох кілець збільшить кількість з'єднаних груп). Всі існуючі ключі та кільця згадуються хоча б один раз.
Вихідні дані
Для кожного тестового випадку виведіть номер випадку, за яким слідує мінімальна кількість операцій прикріплення/від'єднання ключів та мінімальна кількість операцій з'єднання/роз'єднання кілець.
Якщо немає способу розділити ключі, як вказано, виведіть номер випадку та слово impossible замість двох чисел.