시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 11 3 3 27.273%

문제

숭이는 자신이 가신 열쇠더미의 절반을 혜빈이에게 주려고 한다. 열쇠는 나선형을 따라 밀어서 열쇠 고리에 걸거나 분리할 수 있다. 같은 방식으로 열쇠 고리도 서로 연결하거나 분리 할 수 있다. 열쇠 고리에 열쇠를 연결하는 작업은 성가신 작업이기 때문에(숭이는 혜빈이가 손톱에 네일아트를 해주기 때문에 손톱을 다쳐선 안 된다) 이 과정을 최소로 하여 연결하려고 한다.

열쇠를 연결하거나 분리하거나, 열쇠 고리를 연결하거나 분리하는 것은 하나의 작업으로 간주된다. 열쇠를 밀어서 연결하거나 분리하는것은 고리를 연결하거나 분리하는 것에 비해 비해 매우 힘들기 때문에 숭이는 열쇠를 연결하거나 분리하는 과정을 최소로 하려고 한다. 만약 열쇠를 연결하거나 분리하는 횟수가 서로 같다면 열쇠 고리를 연결하거나 분리하는 과정을 최소로 해야 한다.

모든 작업이 완료되면, 숭이는 혜빈이에게 열쇠 더미를 건네준다(정확히 숭이꺼, 혜빈이꺼 두덩이로 분리되어야 한다). 예외가 되는 경우는 숭이가 갖는 열쇠 더미가 없거나 혜빈이에게 줄 수 있는 열쇠 더미가 없는 경우이다. 각각의 열쇠는 반드시 하나의 고리에 연결되어 있어야 한다. 열쇠 고리는 남은것이 생길 수 있다. 이때에는 두 그룹에서 분리시킨다

아래의 왼쪽 그림은 네개의 열쇠와 세개의 고리로 연결되어 있는 초기 상태를 나타낸다. 숭이는 혜빈이에게 2개의 열쇠인 N,R을 주려고 한다. 이때에 두 번의 열쇠 동작과 한번의 고리 동작으로 줄 수 있다. 이러한 결과가 아래의 오른쪽 그림이다.

입력

각각의 테스트 케이스는 하나 또는 여러개의 줄로 이루어져 있다. 각각의 테스트 케이스는 2개 문자로 이루어져 있다. 영어 소문자는 열쇠 고리를 나타내며 대문자는 열쇠를 나타낸다. 입력된 2개의 문자는 열쇠와 고리가 연결된 상태를 나타내거나, 고리와 고리가 연결된 상태를 나타낸다. 테스트 케이스 마지막 줄에는 0이 주어진다.

A부터 M까지의 열쇠는 숭이가 갖고, N부터 Z까지의 열쇠는 혜빈이에게 준다.

두 개의 문자가 모두 대문자인 경우는 없다. 테스트 케이스 내에서 같은 쌍으로 이루어진 문자열은 주어지지 않는다. 각각의 열쇠는 반드시 하나의 고리에 연결되어야 한다. 초기에 주어지는 열쇠 상태에서 고리에는 반드시 열쇠가 연결되어 있다(분리하면서 고리만 존재하는 경우는 발생할 수 있다). 존재하는 모든 열쇠와 고리는 반드시 한번 이상 주어진다.

출력

각각의 테스트 케이스에 대해서 열쇠를 연결하거나 분리하는 최소 횟수와 고리를 연결하거나 분리하는 최소 횟수를 출력한다.

만일 그러한 경우가 없다면 "impossible"을 출력한다.

예제 입력 1

ab
bc
aA
aN
Rb
cB
0
aA
bB
Cc
0
aA
aZ
0
aA
bB
cC
xX
yY
ax
xb
by
yc
0

예제 출력 1

Case 1: 2 1
Case 2: 0 2
Case 3: impossible
Case 4: 0 7
W3sicHJvYmxlbV9pZCI6IjQyMDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZjRcdWMxZTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzIyZFx1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVhYzAwXHVjMmUwIFx1YzVmNFx1YzFlMFx1YjM1NFx1YmJmOFx1Yzc1OCBcdWM4MDhcdWJjMThcdWM3NDQgXHVkNjFjXHViZTQ4XHVjNzc0XHVjNWQwXHVhYzhjIFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzVmNFx1YzFlMFx1YjI5NCBcdWIwOThcdWMxMjBcdWQ2MTVcdWM3NDQgXHViNTMwXHViNzdjIFx1YmMwMFx1YzViNFx1YzExYyBcdWM1ZjRcdWMxZTAgXHVhY2UwXHViOWFjXHVjNWQwIFx1YWM3OFx1YWM3MFx1YjA5OCBcdWJkODRcdWI5YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YmMyOVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM1ZjRcdWMxZTAgXHVhY2UwXHViOWFjXHViM2M0IFx1YzExY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWFjNzBcdWIwOTggXHViZDg0XHViOWFjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM1ZjRcdWMxZTAgXHVhY2UwXHViOWFjXHVjNWQwIFx1YzVmNFx1YzFlMFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzQwIFx1YzEzMVx1YWMwMFx1YzJlMCBcdWM3OTFcdWM1YzVcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwKFx1YzIyZFx1Yzc3NFx1YjI5NCBcdWQ2MWNcdWJlNDhcdWM3NzRcdWFjMDAgXHVjMTkwXHVkMWIxXHVjNWQwIFx1YjEyNFx1Yzc3Y1x1YzU0NFx1ZDJiOFx1Yjk3YyBcdWQ1NzRcdWM4ZmNcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzE5MFx1ZDFiMVx1Yzc0NCBcdWIyZTRcdWNjZDBcdWMxMjAgXHVjNTQ4IFx1YjQxY1x1YjJlNCkgXHVjNzc0IFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTU4XHVjNWVjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzVmNFx1YzFlMFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWFjNzBcdWIwOTggXHViZDg0XHViOWFjXHVkNTU4XHVhYzcwXHViMDk4LCBcdWM1ZjRcdWMxZTAgXHVhY2UwXHViOWFjXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YWM3MFx1YjA5OCBcdWJkODRcdWI5YWNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM3OTFcdWM1YzVcdWM3M2NcdWI4NWMgXHVhYzA0XHVjOGZjXHViNDFjXHViMmU0LiBcdWM1ZjRcdWMxZTBcdWI5N2MgXHViYzAwXHVjNWI0XHVjMTFjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YWM3MFx1YjA5OCBcdWJkODRcdWI5YWNcdWQ1NThcdWIyOTRcdWFjODNcdWM3NDAgXHVhY2UwXHViOWFjXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YWM3MFx1YjA5OCBcdWJkODRcdWI5YWNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNWQwIFx1YmU0NFx1ZDU3NCBcdWJlNDRcdWQ1NzQgXHViOWU0XHVjNmIwIFx1ZDc5OFx1YjRlNFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjMjJkXHVjNzc0XHViMjk0IFx1YzVmNFx1YzFlMFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWFjNzBcdWIwOTggXHViZDg0XHViOWFjXHVkNTU4XHViMjk0IFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YzVmNFx1YzFlMFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWFjNzBcdWIwOTggXHViZDg0XHViOWFjXHVkNTU4XHViMjk0IFx1ZDY5Zlx1YzIxOFx1YWMwMCBcdWMxMWNcdWI4NWMgXHVhYzE5XHViMmU0XHViYTc0IFx1YzVmNFx1YzFlMCBcdWFjZTBcdWI5YWNcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHVhYzcwXHViMDk4IFx1YmQ4NFx1YjlhY1x1ZDU1OFx1YjI5NCBcdWFjZmNcdWM4MTVcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWM3OTFcdWM1YzVcdWM3NzQgXHVjNjQ0XHViOGNjXHViNDE4XHViYTc0LCBcdWMyMmRcdWM3NzRcdWIyOTQgXHVkNjFjXHViZTQ4XHVjNzc0XHVjNWQwXHVhYzhjIFx1YzVmNFx1YzFlMCBcdWIzNTRcdWJiZjhcdWI5N2MgXHVhYzc0XHViMTI0XHVjOTAwXHViMmU0KFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWMyMmRcdWM3NzRcdWFlYmMsIFx1ZDYxY1x1YmU0OFx1Yzc3NFx1YWViYyBcdWI0NTBcdWIzNjlcdWM3NzRcdWI4NWMgXHViZDg0XHViOWFjXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNCkuIFx1YzYwOFx1YzY3OFx1YWMwMCBcdWI0MThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzIyZFx1Yzc3NFx1YWMwMCBcdWFjMTZcdWIyOTQgXHVjNWY0XHVjMWUwIFx1YjM1NFx1YmJmOFx1YWMwMCBcdWM1YzZcdWFjNzBcdWIwOTggXHVkNjFjXHViZTQ4XHVjNzc0XHVjNWQwXHVhYzhjIFx1YzkwNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzVmNFx1YzFlMCBcdWIzNTRcdWJiZjhcdWFjMDAgXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc3NFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzVmNFx1YzFlMFx1YjI5NCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWNlMFx1YjlhY1x1YzVkMCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNWY0XHVjMWUwIFx1YWNlMFx1YjlhY1x1YjI5NCBcdWIwYThcdWM3NDBcdWFjODNcdWM3NzQgXHVjMGRkXHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0Y1x1YzVkMFx1YjI5NCBcdWI0NTAgXHVhZGY4XHViOGY5XHVjNWQwXHVjMTFjIFx1YmQ4NFx1YjlhY1x1YzJkY1x1ZDBhOFx1YjJlNDxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OThcdWM3NTggXHVjNjdjXHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc0MCBcdWIxMjRcdWFjMWNcdWM3NTggXHVjNWY0XHVjMWUwXHVjNjQwIFx1YzEzOFx1YWMxY1x1Yzc1OCBcdWFjZTBcdWI5YWNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWNkMDhcdWFlMzAgXHVjMGMxXHVkMGRjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVjMjJkXHVjNzc0XHViMjk0IFx1ZDYxY1x1YmU0OFx1Yzc3NFx1YzVkMFx1YWM4YyAyXHVhYzFjXHVjNzU4IFx1YzVmNFx1YzFlMFx1Yzc3OCBOLFJcdWM3NDQgXHVjOGZjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjXHVjNWQwIFx1YjQ1MCBcdWJjODhcdWM3NTggXHVjNWY0XHVjMWUwIFx1YjNkOVx1Yzc5MVx1YWNmYyBcdWQ1NWNcdWJjODhcdWM3NTggXHVhY2UwXHViOWFjIFx1YjNkOVx1Yzc5MVx1YzczY1x1Yjg1YyBcdWM5MDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YWNiMFx1YWNmY1x1YWMwMCBcdWM1NDRcdWI3OThcdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9rZXlzLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5MHB4OyB3aWR0aDo1MjlweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTU4XHViMDk4IFx1YjYxMFx1YjI5NCBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWM3NTggXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IDJcdWFjMWMgXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzYwMVx1YzViNCBcdWMxOGNcdWJiMzhcdWM3OTBcdWIyOTQgXHVjNWY0XHVjMWUwIFx1YWNlMFx1YjlhY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAgXHViMzAwXHViYjM4XHVjNzkwXHViMjk0IFx1YzVmNFx1YzFlMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1YjQxYyAyXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YjI5NCBcdWM1ZjRcdWMxZTBcdWM2NDAgXHVhY2UwXHViOWFjXHVhYzAwIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWMwYzFcdWQwZGNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHVhYzcwXHViMDk4LCBcdWFjZTBcdWI5YWNcdWM2NDAgXHVhY2UwXHViOWFjXHVhYzAwIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWMwYzFcdWQwZGNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkFcdWJkODBcdWQxMzAgTVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWM1ZjRcdWMxZTBcdWIyOTQgXHVjMjJkXHVjNzc0XHVhYzAwIFx1YWMxNlx1YWNlMCwgTlx1YmQ4MFx1ZDEzMCBaXHVhZTRjXHVjOWMwXHVjNzU4IFx1YzVmNFx1YzFlMFx1YjI5NCBcdWQ2MWNcdWJlNDhcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjOTAwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWJhYThcdWI0NTAgXHViMzAwXHViYjM4XHVjNzkwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViMGI0XHVjNWQwXHVjMTFjIFx1YWMxOVx1Yzc0MCBcdWMzMGRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjNWY0XHVjMWUwXHViMjk0IFx1YmMxOFx1YjRkY1x1YzJkYyBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2UwXHViOWFjXHVjNWQwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Y2QwOFx1YWUzMFx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjNWY0XHVjMWUwIFx1YzBjMVx1ZDBkY1x1YzVkMFx1YzExYyBcdWFjZTBcdWI5YWNcdWM1ZDBcdWIyOTQgXHViYzE4XHViNGRjXHVjMmRjIFx1YzVmNFx1YzFlMFx1YWMwMCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0KFx1YmQ4NFx1YjlhY1x1ZDU1OFx1YmE3NFx1YzExYyBcdWFjZTBcdWI5YWNcdWI5Y2MgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWJjMWNcdWMwZGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNCkuIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjNWY0XHVjMWUwXHVjNjQwIFx1YWNlMFx1YjlhY1x1YjI5NCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVkNTVjXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YzVmNFx1YzFlMFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWFjNzBcdWIwOTggXHViZDg0XHViOWFjXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWQ2OWZcdWMyMThcdWM2NDAgXHVhY2UwXHViOWFjXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YWM3MFx1YjA5OCBcdWJkODRcdWI5YWNcdWQ1NThcdWIyOTQgXHVjZDVjXHVjMThjIFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1Yzc3YyBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzVjNlx1YjJlNFx1YmE3NCAmcXVvdDtpbXBvc3NpYmxlJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MjA4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS2V5cyIsImRlc2NyaXB0aW9uIjoiPHA+QWRhbSBjYXJyaWVzIGEgYnVuY2ggb2Yga2V5cyBhdHRhY2hlZCB0byBrZXkgcmluZ3MsIHNvbWUgb2Ygd2hpY2ggbWF5IGJlIGNvbm5lY3RlZCB0byBlYWNoIG90aGVyLiBUaGUgcmluZ3MgYXJlIGNvbW1vbiBrZXkgcmluZ3MsIHNvIGEga2V5IGNhbiBiZSBhdHRhY2hlZCB0byBvciBkZXRhY2hlZCBmcm9tIGEgcmluZyBieSBzbGlkaW5nIGFsb25nIHRoZSBzcGlyYWwuIEluIHRoZSBzYW1lIHdheSwgdHdvIHJpbmdzIGNhbiBiZSBjb25uZWN0ZWQgb3IgZGlzY29ubmVjdGVkLiBBZGFtIHdhbnRzIHRvIGdpdmUgc29tZSBvZiB0aGUga2V5cyB0byBCcmVuZGEuIFNpbmNlIG1hbmlwdWxhdGluZyB0aGUga2V5cyBhbmQgcmluZ3MgaXMgb2Z0ZW4gYW4gYW5ub3lpbmcgdGFzayAoYW5kIGFsc28gZGFuZ2Vyb3VzIHRvIG9uZSZyc3F1bztzIFx1ZmIwMW5nZXJuYWlscyksIEFkYW0gaXMgbG9va2luZyBmb3IgYSB3YXkgdG8gbWluaW1pemUgdGhlIG51bWJlciBvZiBrZXkgYW5kIHJpbmcgb3BlcmF0aW9ucy48XC9wPlxyXG5cclxuPHA+RXZlcnkga2V5IGF0dGFjaG1lbnQsIGtleSBkZXRhY2htZW50LCByaW5nIGNvbm5lY3Rpb24sIG9yIHJpbmcgZGlzY29ubmVjdGlvbiBpcyBjb25zaWRlcmVkIG9uZSBvcGVyYXRpb24uIFNpbmNlIG1hbmlwdWxhdGluZyB0d28gcmluZ3MgaXMgc2lnbmlcdWZiMDFjYW50bHkgZWFzaWVyIHRoYW4gc2xpZGluZyBhIGtleSwgd2UgXHVmYjAxcnN0IHdhbnQgdG8gbWluaW1pemUgdGhlIG51bWJlciBvZiBrZXlzIGJlaW5nIGRldGFjaGVkIGFuZCBhdHRhY2hlZC4gQW1vbmcgc29sdXRpb25zIHdpdGggdGhlIHNhbWUgbWluaW1hbCBudW1iZXIgb2Yga2V5IG9wZXJhdGlvbnMsIHlvdSBuZWVkIHRvIFx1ZmIwMW5kIHRoZSBvbmUgd2l0aCB0aGUgbWluaW1hbCBudW1iZXIgb2YgcmluZyBjb25uZWN0aW9ucyBhbmQgZGlzY29ubmVjdGlvbnMuPFwvcD5cclxuXHJcbjxwPldoZW4gYWxsIHRoZSBvcGVyYXRpb25zIGFyZSBjb21wbGV0ZSwgQWRhbSBhbmQgQnJlbmRhIG11c3QgZWFjaCBjYXJyeSBvbmUgY29ubmVjdGVkIGdyb3VwIG9mIHJpbmdzIGFuZCBrZXlzLiBUaGUgb25seSBleGNlcHRpb24gaXMgd2hlbiBlaXRoZXIgb2YgdGhlbSB3b3VsZCBoYXZlIG5vIGtleXMgYXQgYWxsJm1kYXNoO2luIHN1Y2ggYSBjYXNlLCBubyByaW5nIGlzIG5lZWRlZC4gRWFjaCBrZXkgbXVzdCBiZSBhdHRhY2hlZCB0byBleGFjdGx5IG9uZSByaW5nLiBTb21lIHJpbmdzIChidXQgbm90IGtleXMpIG1heSBiZSBjb25zaWRlcmVkIGxlZnRvdmVycyBhbmQgbWF5IHJlbWFpbiBkaXNjb25uZWN0ZWQgZnJvbSB0aGUgdHdvIGdyb3Vwcy48XC9wPlxyXG5cclxuPHA+VGhlIGxlZnQgc2lkZSBvZiB0aGUgZm9sbG93aW5nIFx1ZmIwMWd1cmUgc2hvd3MgYW4gaW5pdGlhbCBjb25cdWZiMDFndXJhdGlvbiBjb25zaXN0aW5nIG9mIGZvdXIga2V5cyBvbiB0aHJlZSByaW5ncy4gQWRhbSB3aXNoZXMgdG8gZ2l2ZSBCcmVuZGEgdGhlIHR3byBrZXlzIGxhYmVsZWQgTiBhbmQgUi4gVGhpcyBjYW4gYmUgYWNjb21wbGlzaGVkIGJ5IHR3byBrZXkgb3BlcmF0aW9ucyBhbmQgb25lIHJpbmcgb3BlcmF0aW9uLCByZXN1bHRpbmcgaW4gdGhlIGNvblx1ZmIwMWd1cmF0aW9uIHNob3duIG9uIHRoZSByaWdodCBzaWRlIG9mIHRoZSBcdWZiMDFndXJlLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tleXMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTkwcHg7IHdpZHRoOjUyOXB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIHRlc3QgY2FzZSBjb250YWlucyBvbmUgb3IgbW9yZSBsaW5lcywgZWFjaCBjb250YWluaW5nIGEgdHdvIGxldHRlciBzdHJpbmcuIExvd2VyY2FzZSBsZXR0ZXJzIChhIC0geikgcmVwcmVzZW50IGtleSByaW5ncyBhbmQgdXBwZXJjYXNlIGxldHRlcnMgKEEgLSBaKSByZXByZXNlbnQga2V5cy4gVGhlIHR3byBsZXR0ZXJzIG9uIGEgbGluZSBzcGVjaWZ5IGVpdGhlciBhIGtleSBhdHRhY2hlZCB0byBhIHJpbmcgb3IgdHdvIHJpbmdzIGNvbm5lY3RlZCB0b2dldGhlci4gVGhlIGVuZCBvZiBlYWNoIHRlc3QgY2FzZSBpcyBkZW5vdGVkIGJ5IGEgbGluZSBjb250YWluaW5nIHRoZSBkaWdpdCB6ZXJvLjxcL3A+XHJcblxyXG48cD5LZXlzIGRlbm90ZWQgYnkgbGV0dGVycyBBIHRocm91Z2ggTSByZW1haW4gd2l0aCBBZGFtLCBhbmQga2V5cyBkZW5vdGVkIGJ5IGxldHRlcnMgTiB0aHJvdWdoIFogYXJlIGdpdmVuIHRvIEJyZW5kYS48XC9wPlxyXG5cclxuPHA+Tm8gbGluZSBjb250YWlucyB0d28gdXBwZXJjYXNlIGxldHRlcnMuIE5vIHBhaXIgb2YgbGV0dGVycyBhcmUgc3BlY2lcdWZiMDFlZCBtb3JlIHRoYW4gb25jZSBpbiB0aGUgc2FtZSB0ZXN0IGNhc2UuIEVhY2gga2V5IGlzIGNvbm5lY3RlZCB0byBleGFjdGx5IG9uZSByaW5nLiBUaGVyZSBhcmUgbm8gJmxkcXVvO2NpcmNsZXMmcmRxdW87IGluIHRoZSByaW5nIGNvblx1ZmIwMWd1cmF0aW9ucyAoZGlzY29ubmVjdGluZyBhbnkgdHdvIHJpbmdzIHdpbGwgaW5jcmVhc2UgdGhlIG51bWJlciBvZiBjb25uZWN0ZWQgZ3JvdXBzKS4gQWxsIGV4aXN0aW5nIGtleXMgYW5kIHJpbmdzIGFyZSBtZW50aW9uZWQgYXQgbGVhc3Qgb25jZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIGRpc3BsYXkgdGhlIGNhc2UgbnVtYmVyIGZvbGxvd2VkIGJ5IHRoZSBtaW5pbWFsIG51bWJlciBvZiBrZXkgYXR0YWNoXC9kZXRhY2ggb3BlcmF0aW9ucyBhbmQgdGhlIG1pbmltYWwgbnVtYmVyIG9mIHJpbmcgY29ubmVjdFwvZGlzY29ubmVjdCBvcGVyYXRpb25zLjxcL3A+XHJcblxyXG48cD5JZiB0aGVyZSBpcyBubyB3YXkgdG8gc3BsaXQgdGhlIGtleXMgYXMgcmVxdWVzdGVkLCBkaXNwbGF5IHRoZSBjYXNlIG51bWJlciBhbmQgdGhlIHdvcmQgaW1wb3NzaWJsZSBpbnN0ZWFkIG9mIHRoZSB0d28gaW50ZWdlcnMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ICPC > World Finals > 2012 World Finals F번

  • 문제를 번역한 사람: lll4592