시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB111373351.562%

문제

sed는 입력으로 주어지는 문자열에 등장하는 문자열 α를 다른 문자열 β로 바꾸는데 사용되는 리눅스 유틸이다. 여기서 입력으로 주어지는 문자열은 파일의 각 한 줄이다. sed는 다음과 같은 2가지 과정을 거친다.

  1. 입력 문자열에서 겹치지 않는 α를 표시한다. 이때, α가 서로 겹칠 수는 있다. 만약, 겹치지 않게 선택하는 경우가 여러 가지 있을 때는 가장 왼쪽 것을 선택한다.
  2. 위에서 표시한 모둔 문자열 α를 문자열 β로 바꾼다. 나머지 문자는 바꾸지 않고 그대로 놔둔다.

예를 들어, α가 "aa"이고, β가 "bca", 입력 문자열이 "aaxaaa"라면 sed를 실행한 결과는 "bcaxbcaa"가 된다. ("aaxbcaa", "bcaxabca"는 될 수 없다) 이 결과 "bcaxbcaa"를 가지고 다시 sed를 실행하면 결과는 "bcaxbcbca"가 된다.

문자열을 바꾸는 규칙의 쌍 (αi, βi) (i = 1,2,...,n), 초기 문자열 γ, 최종 문자열 δ가 주어진다. 이때, sed를 이용해서 γ를 δ로 바꿀 때, 문자열 바꾸는 회수의 최솟값을 구하려고 한다.

하나의 규칙(αi, βi)은 위에서 설명한 것 같이, 입력 문자열에서 겹치지 않는 모든 부분 문자열 αi를 βi로 동시에 바꾸는 것을 의미한다.

한 규칙(αi, βi)을 여러 번 사용해도 되고, 사용하지 않아도 된다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 다음과 같은 형식이다.

n
α1 β1
α2 β2
...
αn βn
γ
δ

n은 문자열을 바꾸는 규칙의 쌍의 개수이다. αi와 βi는 공백으로 구분되어 있으며, 1 ≤ |αi| < |βi| ≤ 10을 만족한다. (|s|는 문자열 s의 길이) 모든 i≠j에 대해서 αi≠αj이며, n ≤ 10, 1 ≤ |γ| < |δ| ≤ 10 이다. 모든 문자열을 알파벳 소문자로만 이루어져 있고, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, γ를 δ로 바꿀 때 필요한 문자열 바꾸는 회수의 최솟값을 출력한다. 만약 γ를 δ로 바꿀 수 없다면, -1을 출력한다.

예제 입력 1

2
a bb
b aa
a
bbbbbbbb
1
a aa
a
aaaaa
3
ab aab
abc aadc
ad dee
abc
deeeeeeeec
10
a abc
b bai
c acf
d bed
e abh
f fag
g abe
h bag
i aaj
j bbb
a
abacfaabe
0

예제 출력 1

3
-1
7
4
W3sicHJvYmxlbV9pZCI6IjM4NzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJzZWQgXHVjNzc0XHVjNmE5IiwiZGVzY3JpcHRpb24iOiI8cD5zZWRcdWIyOTQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDAgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNCAmYWxwaGE7XHViOTdjIFx1YjJlNFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWM1ZjQgJmJldGE7XHViODVjIFx1YmMxNFx1YWZiOFx1YjI5NFx1YjM3MCBcdWMwYWNcdWM2YTlcdWI0MThcdWIyOTQgXHViOWFjXHViMjA1XHVjMmE0IFx1YzcyMFx1ZDJmOFx1Yzc3NFx1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1ZDMwY1x1Yzc3Y1x1Yzc1OCBcdWFjMDEgXHVkNTVjIFx1YzkwNFx1Yzc3NFx1YjJlNC4gc2VkXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgMlx1YWMwMFx1YzljMCBcdWFjZmNcdWM4MTVcdWM3NDQgXHVhYzcwXHVjZTVjXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1Yzc4NVx1YjgyNSBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVhY2I5XHVjZTU4XHVjOWMwIFx1YzU0YVx1YjI5NCAmYWxwaGE7XHViOTdjIFx1ZDQ1Y1x1YzJkY1x1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCAmYWxwaGE7XHVhYzAwIFx1YzExY1x1Yjg1YyBcdWFjYjlcdWNlNjAgXHVjMjE4XHViMjk0IFx1Yzc4OFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHVhYzhjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMCBcdWM3ODhcdWM3NDQgXHViNTRjXHViMjk0IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVhYzgzXHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzA0XHVjNWQwXHVjMTFjIFx1ZDQ1Y1x1YzJkY1x1ZDU1YyBcdWJhYThcdWI0NTQgXHViYjM4XHVjNzkwXHVjNWY0ICZhbHBoYTtcdWI5N2MgXHViYjM4XHVjNzkwXHVjNWY0ICZiZXRhO1x1Yjg1YyBcdWJjMTRcdWFmYmNcdWIyZTQuIFx1YjA5OFx1YmEzOFx1YzljMCBcdWJiMzhcdWM3OTBcdWIyOTQgXHViYzE0XHVhZmI4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWFkZjhcdWIzMDBcdWI4NWMgXHViMTk0XHViNDU0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICZhbHBoYTtcdWFjMDAgJnF1b3Q7YWEmcXVvdDtcdWM3NzRcdWFjZTAsICZiZXRhO1x1YWMwMCAmcXVvdDtiY2EmcXVvdDssIFx1Yzc4NVx1YjgyNSBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgJnF1b3Q7YWF4YWFhJnF1b3Q7XHViNzdjXHViYTc0IHNlZFx1Yjk3YyBcdWMyZTRcdWQ1ODlcdWQ1NWMgXHVhY2IwXHVhY2ZjXHViMjk0ICZxdW90O2JjYXhiY2FhJnF1b3Q7XHVhYzAwIFx1YjQxY1x1YjJlNC4gKCZxdW90O2FheGJjYWEmcXVvdDssICZxdW90O2JjYXhhYmNhJnF1b3Q7XHViMjk0IFx1YjQyMCBcdWMyMTggXHVjNWM2XHViMmU0KSBcdWM3NzQgXHVhY2IwXHVhY2ZjICZxdW90O2JjYXhiY2FhJnF1b3Q7XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWIyZTRcdWMyZGMgc2VkXHViOTdjIFx1YzJlNFx1ZDU4OVx1ZDU1OFx1YmE3NCBcdWFjYjBcdWFjZmNcdWIyOTQgJnF1b3Q7YmNheGJjYmNhJnF1b3Q7XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YmMxNFx1YWZiOFx1YjI5NCBcdWFkZGNcdWNlNTlcdWM3NTggXHVjMzBkICgmYWxwaGE7PHN1Yj5pPFwvc3ViPiwgJmJldGE7PHN1Yj5pPFwvc3ViPikgKGkgPSAxLDIsLi4uLG4pLCBcdWNkMDhcdWFlMzAgXHViYjM4XHVjNzkwXHVjNWY0ICZnYW1tYTssIFx1Y2Q1Y1x1Yzg4NSBcdWJiMzhcdWM3OTBcdWM1ZjQgJmRlbHRhO1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0Yywgc2VkXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyAmZ2FtbWE7XHViOTdjICZkZWx0YTtcdWI4NWMgXHViYzE0XHVhZmMwIFx1YjU0YywgXHViYjM4XHVjNzkwXHVjNWY0IFx1YmMxNFx1YWZiOFx1YjI5NCBcdWQ2OGNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWFkZGNcdWNlNTkoJmFscGhhOzxzdWI+aTxcL3N1Yj4sICZiZXRhOzxzdWI+aTxcL3N1Yj4pXHVjNzQwIFx1YzcwNFx1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWMgXHVhYzgzIFx1YWMxOVx1Yzc3NCwgXHVjNzg1XHViODI1IFx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMFx1YzExYyBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YmFhOFx1YjRlMCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0ICZhbHBoYTs8c3ViPmk8XC9zdWI+XHViOTdjICZiZXRhOzxzdWI+aTxcL3N1Yj5cdWI4NWMgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YmMxNFx1YWZiOFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NWMgXHVhZGRjXHVjZTU5KCZhbHBoYTs8c3ViPmk8XC9zdWI+LCAmYmV0YTs8c3ViPmk8XC9zdWI+KVx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YzBhY1x1YzZhOVx1ZDU3NFx1YjNjNCBcdWI0MThcdWFjZTAsIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NDRcdWIzYzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxublxyXG4mYWxwaGE7PHN1Yj4xPFwvc3ViPiAmYmV0YTs8c3ViPjE8XC9zdWI+XHJcbiZhbHBoYTs8c3ViPjI8XC9zdWI+ICZiZXRhOzxzdWI+MjxcL3N1Yj5cclxuLi4uXHJcbiZhbHBoYTs8c3ViPm48XC9zdWI+ICZiZXRhOzxzdWI+bjxcL3N1Yj5cclxuJmdhbW1hO1xyXG4mZGVsdGE7PFwvcHJlPlxyXG5cclxuPHA+blx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViYzE0XHVhZmI4XHViMjk0IFx1YWRkY1x1Y2U1OVx1Yzc1OCBcdWMzMGRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiAmYWxwaGE7PHN1Yj5pPFwvc3ViPlx1YzY0MCAmYmV0YTs8c3ViPmk8XC9zdWI+XHViMjk0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCAxICZsZTsgfCZhbHBoYTs8c3ViPmk8XC9zdWI+fCAmbHQ7IHwmYmV0YTs8c3ViPmk8XC9zdWI+fCAmbGU7IDEwXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC4gKHxzfFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjQgc1x1Yzc1OCBcdWFlMzhcdWM3NzQpIFx1YmFhOFx1YjRlMCBpJm5lO2pcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjICZhbHBoYTs8c3ViPmk8XC9zdWI+Jm5lOyZhbHBoYTs8c3ViPmo8XC9zdWI+XHVjNzc0XHViYTcwLCBuICZsZTsgMTAsIDEgJmxlOyB8JmdhbW1hO3wgJmx0OyB8JmRlbHRhO3wgJmxlOyAxMCBcdWM3NzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCAmZ2FtbWE7XHViOTdjICZkZWx0YTtcdWI4NWMgXHViYzE0XHVhZmMwIFx1YjU0YyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViYjM4XHVjNzkwXHVjNWY0IFx1YmMxNFx1YWZiOFx1YjI5NCBcdWQ2OGNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkICZnYW1tYTtcdWI5N2MgJmRlbHRhO1x1Yjg1YyBcdWJjMTRcdWFmYzAgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YmE3NCwgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM4NzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSZXBlYXRlZCBTdWJzdGl0dXRpb24gd2l0aCBTZWQiLCJkZXNjcmlwdGlvbiI6IjxwPkRvIHlvdSBrbm93ICZsZHF1bztzZWQsJnJkcXVvOyBhIHRvb2wgcHJvdmlkZWQgd2l0aCBVbml4PyBJdHMgbW9zdCBwb3B1bGFyIHVzZSBpcyB0byBzdWJzdGl0dXRlIGV2ZXJ5IG9jY3VycmVuY2Ugb2YgYSBzdHJpbmcgJmFscGhhOyBjb250YWluZWQgaW4gdGhlIGlucHV0IHN0cmluZyAoYWN0dWFsbHkgZWFjaCBpbnB1dCBsaW5lKSB3aXRoIGFub3RoZXIgc3RyaW5nICZiZXRhOy4gTW9yZSBwcmVjaXNlbHksIGl0IHByb2NlZWRzIGFzIGZvbGxvd3MuPFwvcD5cclxuXHJcbjxwPldpdGhpbiB0aGUgaW5wdXQgc3RyaW5nLCBldmVyeSBub24tb3ZlcmxhcHBpbmcgKGJ1dCBwb3NzaWJseSBhZGphY2VudCkgb2NjdXJyZW5jZXMgb2YgJmFscGhhOyBhcmUgbWFya2VkLiBJZiB0aGVyZSBpcyBtb3JlIHRoYW4gb25lIHBvc3NpYmlsaXR5IGZvciBub24tb3ZlcmxhcHBpbmcgbWF0Y2hpbmcsIHRoZSBsZWZ0bW9zdCBvbmUgaXMgY2hvc2VuLjxiciBcLz5cclxuRWFjaCBvZiB0aGUgbWFya2VkIG9jY3VycmVuY2VzIGlzIHN1YnN0aXR1dGVkIHdpdGggJmJldGE7IHRvIG9idGFpbiB0aGUgb3V0cHV0IHN0cmluZzsgb3RoZXIgcGFydHMgb2YgdGhlIGlucHV0IHN0cmluZyByZW1haW4gaW50YWN0LjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgd2hlbiAmYWxwaGE7IGlzICZsZHF1bzthYSZyZHF1bzsgYW5kICZiZXRhOyBpcyAmbGRxdW87YmNhJnJkcXVvOywgYW4gaW5wdXQgc3RyaW5nICZsZHF1bzthYXhhYWEmcmRxdW87IHdpbGwgcHJvZHVjZSAmbGRxdW87YmNheGJjYWEmcmRxdW87LCBidXQgbm90ICZsZHF1bzthYXhiY2FhJnJkcXVvOyBub3IgJmxkcXVvO2JjYXhhYmNhJnJkcXVvOy4gRnVydGhlciBhcHBsaWNhdGlvbiBvZiB0aGUgc2FtZSBzdWJzdGl0dXRpb24gdG8gdGhlIHN0cmluZyAmbGRxdW87YmNheGJjYWEmcmRxdW87IHdpbGwgcmVzdWx0IGluICZsZHF1bztiY2F4YmNiY2EmcmRxdW87LCBidXQgdGhpcyBpcyBhbm90aGVyIHN1YnN0aXR1dGlvbiwgd2hpY2ggaXMgY291bnRlZCBhcyB0aGUgc2Vjb25kIG9uZS48XC9wPlxyXG5cclxuPHA+SW4gdGhpcyBwcm9ibGVtLCBhIHNldCBvZiBzdWJzdGl0dXRpb24gcGFpcnMgKCZhbHBoYTs8c3ViPmk8XC9zdWI+LCAmYmV0YTs8c3ViPmk8XC9zdWI+KSAoaSA9IDEsIDIsIC4gLiAuICwgbiksIGFuIGluaXRpYWwgc3RyaW5nICZnYW1tYTssIGFuZCBhIGZpbmFsIHN0cmluZyAmZGVsdGE7IGFyZSBnaXZlbiwgYW5kIHlvdSBtdXN0IGludmVzdGlnYXRlIGhvdyB0byBwcm9kdWNlICZkZWx0YTsgZnJvbSAmZ2FtbWE7IHdpdGggYSBtaW5pbXVtIG51bWJlciBvZiBzdWJzdGl0dXRpb25zLiBBIHNpbmdsZSBzdWJzdGl0dXRpb24gKCZhbHBoYTs8c3ViPmk8XC9zdWI+LCAmYmV0YTs8c3ViPmk8XC9zdWI+KSBoZXJlIG1lYW5zIHNpbXVsdGFuZW91c2x5IHN1YnN0aXR1dGluZyBhbGwgdGhlIG5vbi1vdmVybGFwcGluZyBvY2N1cnJlbmNlcyBvZiAmYWxwaGE7PHN1Yj5pPFwvc3ViPiwgaW4gdGhlIHNlbnNlIGRlc2NyaWJlZCBhYm92ZSwgd2l0aCAmYmV0YTs8c3ViPmk8XC9zdWI+LjxcL3A+XHJcblxyXG48cD5Zb3UgbWF5IHVzZSBhIHNwZWNpXHVmYjAxYyBzdWJzdGl0dXRpb24gKCZhbHBoYTs8c3ViPmk8XC9zdWI+LCAmYmV0YTs8c3ViPmk8XC9zdWI+KSBtdWx0aXBsZSB0aW1lcywgaW5jbHVkaW5nIHplcm8gdGltZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgbXVsdGlwbGUgZGF0YXNldHMsIGVhY2ggaW4gdGhlIGZvbGxvd2luZyBmb3JtYXQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbm5cclxuJmFscGhhOzxzdWI+MTxcL3N1Yj4gJmJldGE7PHN1Yj4xPFwvc3ViPlxyXG4mYWxwaGE7PHN1Yj4yPFwvc3ViPiAmYmV0YTs8c3ViPjI8XC9zdWI+XHJcbi4uLlxyXG4mYWxwaGE7PHN1Yj5uPFwvc3ViPiAmYmV0YTs8c3ViPm48XC9zdWI+XHJcbiZnYW1tYTtcclxuJmRlbHRhOzxcL3ByZT5cclxuXHJcbjxwPm4gaXMgYSBwb3NpdGl2ZSBpbnRlZ2VyIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiBwYWlycy4gJmFscGhhO2kgYW5kICZiZXRhO2kgYXJlIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gWW91IG1heSBhc3N1bWUgdGhhdCAxICZsZTsgfCZhbHBoYTs8c3ViPmk8XC9zdWI+fCAmbHQ7IHwmYmV0YTs8c3ViPmk8XC9zdWI+fCAmbGU7IDEwIGZvciBhbnkgaSAofHN8IG1lYW5zIHRoZSBsZW5ndGggb2YgdGhlIHN0cmluZyBzKSwgJmFscGhhOzxzdWI+aTxcL3N1Yj4gJm5lOyAmYWxwaGE7PHN1Yj5qPFwvc3ViPiBmb3IgYW55IGkgJm5lOyBqLCBuICZsZTsgMTAgYW5kIDEgJmxlOyB8JmdhbW1hO3wgJmx0OyB8JmRlbHRhO3wgJmxlOyAxMC4gQWxsIHRoZSBzdHJpbmdzIGNvbnNpc3Qgc29sZWx5IG9mIGxvd2VyY2FzZSBsZXR0ZXJzLiBUaGUgZW5kIG9mIHRoZSBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgemVyby48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhc2V0LCBvdXRwdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHN1YnN0aXR1dGlvbnMgdG8gb2J0YWluICZkZWx0YTsgZnJvbSAmZ2FtbWE7LiBJZiAmZGVsdGE7IGNhbm5vdCBiZSBwcm9kdWNlZCBmcm9tICZnYW1tYTsgd2l0aCB0aGUgZ2l2ZW4gc2V0IG9mIHN1YnN0aXR1dGlvbnMsIG91dHB1dCAtMS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2009 in Tokyo B번