열쇠

숭이는 자신이 가진 열쇠 더미의 절반을 혜빈이에게 주려고 한다. 열쇠는 나선을 따라 밀어 넣어 열쇠고리에 끼우거나 빼낼 수 있고, 열쇠고리끼리도 같은 방식으로 서로 연결하거나 분리할 수 있다.

열쇠 하나를 고리에 끼우거나 빼는 것도, 고리 하나를 다른 고리에 연결하거나 분리하는 것도 각각 한 번의 작업으로 센다. 그런데 열쇠를 밀어 넣는 작업은 고리를 연결하거나 분리하는 작업보다 훨씬 힘들다(혜빈이가 손톱에 네일아트를 해 주기 때문에 손톱을 다치면 안 된다). 그래서 숭이는 먼저 열쇠를 끼우거나 빼는 작업의 횟수를 최소로 하고, 그 횟수가 같은 방법이 여러 가지라면 그중에서 고리를 연결하거나 분리하는 작업의 횟수를 최소로 하려고 한다.

모든 작업이 끝나면 열쇠 더미는 정확히 두 덩이, 즉 숭이가 가질 덩이와 혜빈이에게 줄 덩이로 나뉘어야 한다. 대문자 A부터 M까지의 열쇠는 숭이가 갖고, N부터 Z까지의 열쇠는 혜빈이가 갖는다. 각 덩이는 하나로 연결되어 있어야 하며, 모든 열쇠는 반드시 어떤 고리 하나에 끼워져 있어야 한다. 두 사람 중 한쪽에게 줄 열쇠가 하나도 없다면 굳이 두 덩이로 나눌 필요는 없다. 작업 도중 열쇠가 하나도 없는 빈 고리가 남을 수 있는데, 이런 고리는 두 덩이 어느 쪽에도 속하지 않도록 따로 떼어 둔다.

예를 들어 네 개의 열쇠가 세 개의 고리에 끼워진 상태에서 숭이가 혜빈이에게 열쇠 N과 R을 주려고 한다면, 열쇠 작업 두 번과 고리 작업 한 번으로 두 덩이로 나눌 수 있다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 두 문자가 적힌 여러 줄과, 마지막에 0만 적힌 한 줄로 끝난다. 소문자는 열쇠고리를, 대문자는 열쇠를 나타낸다. 한 줄의 두 문자는 열쇠가 고리에 끼워진 상태(열쇠, 고리)이거나 고리끼리 연결된 상태(고리, 고리)를 뜻한다. 입력은 파일의 끝에서 끝난다.

두 문자가 모두 대문자인 경우는 없다. 한 테스트 케이스 안에서 같은 쌍은 두 번 주어지지 않는다. 각 열쇠는 정확히 하나의 고리에만 끼워져 있으며, 처음 주어지는 상태에서는 모든 고리에 열쇠가 적어도 하나 끼워져 있다(작업을 하다 보면 열쇠 없는 고리가 생길 수는 있다). 등장하는 모든 열쇠와 고리는 입력에 적어도 한 번씩 나타난다.

각 테스트 케이스마다 Case x: a b 형식으로 한 줄에 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호, a는 열쇠를 끼우거나 빼는 작업의 최소 횟수, b는 고리를 연결하거나 분리하는 작업의 최소 횟수이다. 필요한 두 덩이로 나누는 것이 불가능하면 대신 Case x: impossible을 출력한다.