시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 883 416 315 51.895%

문제

좋은 문자열은 다음과 같이 정의된다.

  1. ab 는 좋은 문자열이다.
  2. 만약 문자열 [S]가 좋은 문자열이라면, 오른쪽과 왼쪽 끝에 각각 a와 b를 추가한 문자열 a[S]b 또한 좋은 문자열이다.
  3. 만약 문자열 [S]와 [T]가 좋은 문자열이라면 이들을 붙여 쓴 [S][T] 또한 좋은 문자열이다.

어떤 두 좋은 문자열 A와 B가 주어진다. 문자열 A를 '인접한 두 문자를 서로 바꾸는' 연산을 통해 문자열 B로 바꾸려고 한다. 이때 필요한 연산의 수를 구하는 프로그램을 작성하시오. A를 B로 바꾸는 중에 나타나는 문자열도 모두 좋은 문자열이어야 한다.

예를 들어, A = aabbabab 이고 B = aaaabbbb라 해 보자. 그렇다면 다음과 같이 5번의 연산을 통해 A를 B로 변환할 수 있다.

aabbabab → aabbaabb → aabababb → aabaabbb → aaababbb → aaaabbbb

입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각각의 테스트 케이스마다, 한 줄에 문자열 A, B가 공백으로 분리되어 주어진다. 이때 A와 B는 좋은 문자열이며, 각각의 길이는 2 이상 100,000 이하이다.

출력

T줄에 걸쳐서, 각 테스트 케이스에서 주어진 문자열 A를 문자열 B로 변환할 때 필요한 연산의 수를 출력하시오.

만약 변환이 불가능한 경우 -1을 출력한다.

예제 입력 1

2
aabbabab aaaabbbb
aabbab abaabb

예제 출력 1

5
2
W3sicHJvYmxlbV9pZCI6IjEwNDUzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViYjM4XHVjNzkwXHVjNWY0IFx1YmNjMFx1ZDY1OCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjODhiXHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzgxNVx1Yzc1OFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5hYiBcdWIyOTQgXHVjODhiXHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViOWNjXHVjNTdkIFx1YmIzOFx1Yzc5MFx1YzVmNCBbU11cdWFjMDAgXHVjODhiXHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1Yjc3Y1x1YmE3NCwmbmJzcDtcdWM2MjRcdWI5NzhcdWNhYmRcdWFjZmMgXHVjNjdjXHVjYWJkIFx1YjA1ZFx1YzVkMCBcdWFjMDFcdWFjMDEmbmJzcDthXHVjNjQwIGJcdWI5N2MgXHVjZDk0XHVhYzAwXHVkNTVjIFx1YmIzOFx1Yzc5MFx1YzVmNCBhW1NdYiBcdWI2MTBcdWQ1NWMgXHVjODhiXHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViOWNjXHVjNTdkIFx1YmIzOFx1Yzc5MFx1YzVmNCBbU11cdWM2NDAgW1RdXHVhYzAwIFx1Yzg4Ylx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWI3N2NcdWJhNzQgXHVjNzc0XHViNGU0XHVjNzQ0IFx1YmQ5OVx1YzVlYyBcdWM0ZjQgW1NdW1RdIFx1YjYxMFx1ZDU1YyBcdWM4OGJcdWM3NDAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWI0NTAgXHVjODhiXHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNCBBXHVjNjQwIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjQgQVx1Yjk3YyAmIzM5O1x1Yzc3OFx1YzgxMVx1ZDU1YyBcdWI0NTAgXHViYjM4XHVjNzkwXHViOTdjIFx1YzExY1x1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQmIzM5OyBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVkMWI1XHVkNTc0IFx1YmIzOFx1Yzc5MFx1YzVmNCBCXHViODVjIFx1YmMxNFx1YWZiOFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNWYwXHVjMGIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gQVx1Yjk3YyBCXHViODVjIFx1YmMxNFx1YWZiOFx1YjI5NCBcdWM5MTFcdWM1ZDAgXHViMDk4XHVkMGMwXHViMDk4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1YjNjNCBcdWJhYThcdWI0NTAgXHVjODhiXHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIEEgPSBhYWJiYWJhYiBcdWM3NzRcdWFjZTAgQiA9IGFhYWFiYmJiXHViNzdjIFx1ZDU3NCBcdWJjZjRcdWM3OTAuIFx1YWRmOFx1YjgwN1x1YjJlNFx1YmE3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IDVcdWJjODhcdWM3NTggXHVjNWYwXHVjMGIwXHVjNzQ0IFx1ZDFiNVx1ZDU3NCBBXHViOTdjIEJcdWI4NWMgXHViY2MwXHVkNjU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmFhYmJhPHU+YmE8XC91PmIgJnJhcnI7IGFhYjx1PmJhPFwvdT5hYmIgJnJhcnI7IGFhYmE8dT5iYTxcL3U+YmIgJnJhcnI7IGFhPHU+YmE8XC91PmFiYmIgJnJhcnI7IGFhYTx1PmJhPFwvdT5iYmIgJnJhcnI7IGFhYWFiYmJiPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM3OTBcdWM1ZjQgQSwgQlx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHViZDg0XHViOWFjXHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjIEFcdWM2NDAgQlx1YjI5NCBcdWM4OGJcdWM3NDAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViYTcwLCBcdWFjMDFcdWFjMDFcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDIgXHVjNzc0XHVjMGMxIDEwMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjLCBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzQmbmJzcDtcdWJiMzhcdWM3OTBcdWM1ZjQgQVx1Yjk3YyBcdWJiMzhcdWM3OTBcdWM1ZjQgQlx1Yjg1YyBcdWJjYzBcdWQ2NThcdWQ1NjAgXHViNTRjIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM1ZjBcdWMwYjBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIFx1YmNjMFx1ZDY1OFx1Yzc3NCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhY2JkXHVjNmIwIC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDQ1MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN0cmluZyBUcmFuc2Zvcm1hdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+QSBzdHJpbmcgaXMgY2FsbGVkIHRvIGJlIHdlbGwtZm9ybWVkIGlmIGl0IGNhbiBiZSBnZW5lcmF0ZWQgYnkgdGhlIGZvbGxvd2luZyBydWxlczo8XC9wPlxyXG5cclxuPG9sIHN0eWxlPVwibGlzdC1zdHlsZS10eXBlOmxvd2VyLWFscGhhXCI+XHJcblx0PGxpPjxjb2RlPmFiPFwvY29kZT4gaXMgYSB3ZWxsLWZvcm1lZCBzdHJpbmcuPFwvbGk+XHJcblx0PGxpPklmIDxjb2RlPlM8XC9jb2RlPiBpcyBhIHdlbGwtZm9ybWVkIHN0cmluZywgPGNvZGU+YVNiPFwvY29kZT4gaXMgYWxzbyB3ZWxsLWZvcm1lZC48XC9saT5cclxuXHQ8bGk+SWYgPGNvZGU+UzxcL2NvZGU+IGFuZCA8Y29kZT5UPFwvY29kZT4gYXJlIHdlbGwtZm9ybWVkIHN0cmluZ3MsIDxjb2RlPlNUPFwvY29kZT4gaXMgYWxzbyB3ZWxsLWZvcm1lZC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgPGNvZGU+YWFiYmFiYWI8XC9jb2RlPiwgPGNvZGU+YWJhYmFiYWI8XC9jb2RlPiwgYW5kIDxjb2RlPmFhYWFiYmJiPFwvY29kZT4gYXJlIHdlbGwtZm9ybWVkIHN0cmluZ3MuPFwvcD5cclxuXHJcbjxwPkZvciB0d28gd2VsbC1mb3JtZWQgc3RyaW5ncywgQSBhbmQgQiwgd2Ugd2FudCB0byB0cmFuc2Zvcm0gQSBpbnRvIEIgYnkgcGVyZm9ybWluZyBzdWNjZXNzaXZlbHkgdGhlIG9wZXJhdGlvbiBvZiBleGNoYW5naW5nIGFkamFjZW50IGNoYXJhY3RlcnMuIEFmdGVyIHBlcmZvcm1pbmcgZWFjaCBvcGVyYXRpb24sIHRoZSBzdHJpbmcgc2hvdWxkIGJlIHdlbGwtZm9ybWVkLiBMZXQgQSA9IDxjb2RlPmFhYmJhYmFiPFwvY29kZT4gYW5kIEIgPSA8Y29kZT5hYWFhYmJiYjxcL2NvZGU+LiBUaGVuIEEgY2FuIGJlIHRyYW5zZm9ybWVkIGludG8gQiBieSBmaXZlIG9wZXJhdGlvbnMgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHA+PGNvZGU+YWFiYmE8dT5iYTxcL3U+YjxcL2NvZGU+ICZyYXJyOyA8Y29kZT5hYWI8dT5iYTxcL3U+YWJiPFwvY29kZT4gJnJhcnI7IDxjb2RlPmFhYmE8dT5iYTxcL3U+YmI8XC9jb2RlPiAmcmFycjsgPGNvZGU+YWE8dT5iYTxcL3U+YWJiYjxcL2NvZGU+ICZyYXJyOyA8Y29kZT5hYWE8dT5iYTxcL3U+YmJiPFwvY29kZT4gJnJhcnI7IDxjb2RlPmFhYWFiYmJiPFwvY29kZT4uPFwvcD5cclxuXHJcbjxwPkdpdmVuIHR3byB3ZWxsLWZvcm1lZCBzdHJpbmdzLCBBIGFuZCBCLCB5b3UgaGF2ZSB0byBmaW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiBvcGVyYXRpb25zIHdoaWNoIGFyZSBuZWVkZWQgZm9yIHRyYW5zZm9ybWluZyBBIGludG8gQi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBsaW5lIGNvbnRhaW5pbmcgdHdvIHdlbGwtZm9ybWVkIHN0cmluZ3MgQSBhbmQgQiB3aGljaCBhcmUgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiBUaGUgbGVuZ3RoIG9mIEEgaXMgdGhlIHNhbWUgYXMgdGhlIGxlbmd0aCBvZiBCLCBhbmQgaXMgYXQgbGVhc3QgMiBhbmQgYXQgbW9zdCAxMDAsMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiB0aGUgbWluaW11bSBudW1iZXIgb2YgdGhlIG9wZXJhdGlvbnMgd2hpY2ggYXJlIG5lZWRlZCBmb3IgdHJhbnNmb3JtaW5nIEEgaW50byBCLiBJZiB0aGUgdHJhbnNmb3JtYXRpb24gaXMgaW1wb3NzaWJsZSwgcHJpbnQgLTEuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2014 H번