F. 열쇠

Adam은 열쇠고리에 매달린 열쇠 꾸러미를 들고 다니는데, 고리끼리 서로 연결되어 있을 수도 있다. 고리는 흔한 열쇠고리라서, 나선을 따라 밀면 열쇠를 고리에 끼우거나 뺄 수 있다. 같은 방법으로 두 고리를 연결하거나 분리할 수도 있다. Adam은 열쇠 중 일부를 Brenda에게 주고 싶다. 열쇠와 고리를 다루는 일은 종종 짜증 나는(그리고 손톱에 위험한) 작업이므로, Adam은 열쇠와 고리 조작 횟수를 최소화하는 방법을 찾고 있다. 열쇠 끼우기, 열쇠 빼기, 고리 연결, 고리 분리는 각각 한 번의 조작(ope\(ra- ti\)on)으로 센다. 고리 두 개를 다루는 것이 열쇠를 미는 것보다 훨씬 쉬우므로, 먼저 빼고 끼우는 열쇠 조작의 횟수를 최소화하고자 한다. 열쇠 조작 횟수가 같은 최소인 해들 중에서는 고리 연결·분리 횟수가 최소인 해를 찾아야 한다. 모든 조작이 끝나면 Adam과 Brenda는 각각 하나로 연결된 고리·열쇠 묶음을 지녀야 한다. 유일한 예외는 어느 한쪽이 열쇠를 하나도 갖지 않는 경우로, 그때는 고리도 필요 없다. 각 열쇠는 정확히 하나의 고리에 끼워져 있어야 한다. 일부 고리는(열쇠는 아님) 남는 것으로 간주되어 두 묶음과 분리된 채 남아 있을 수 있다. 다음 그림의 왼쪽은 고리 세 개에 열쇠 네 개가 있는 초기 배치를 보여 준다. Adam은 N과 R이라고 표시된 두 열쇠를 Brenda에게 주려 한다. 이는 열쇠 조작 두 번과 고리 조작 한 번으로 가능하며, 그 결과 배치가 그림의 오른쪽에 나와 있다.

각 테스트 케이스는 한 줄 이상으로 이루어지며, 각 줄에는 두 글자로 된 문자열이 있다. 소문자(\(a - z\))는 열쇠고리를, 대문자(\(A - Z\))는 열쇠를 나타낸다. 한 줄의 두 글자는 고리에 끼워진 열쇠 하나이거나 서로 연결된 두 고리를 나타낸다. 각 테스트 케이스의 끝은 숫자 0이 있는 줄로 표시된다. A부터 M까지의 글자로 표시된 열쇠는 Adam이 갖고, N부터 Z까지의 글자로 표시된 열쇠는 Brenda에게 준다. 대문자 두 개가 있는 줄은 없다. 같은 테스트 케이스에서 같은 글자 쌍이 두 번 이상 주어지지 않는다. 각 열쇠는 정확히 하나의 고리에 연결되어 있다. 고리 배치에 “원”은 없다(어떤 두 고리를 분리해도 연결된 묶음의 수가 늘어난다). 존재하는 모든 열쇠와 고리는 적어도 한 번 언급된다.

각 테스트 케이스마다 케이스 번호와 함께 열쇠 끼우기/빼기(atta\(ch/de\)tach) 조작(op\(er- at\)ions)의 최소 횟수와 고리 연결/분리(conne\(ct/di\)sconnect) 조작의 최소 횟수를 출력한다. 요청대로 열쇠를 나눌 방법이 없으면 두 정수 대신 케이스 번호와 impossible을 출력한다.

생성자가 기록되지 않았습니다.

출처 ICPC World Finals 2012