시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 850 392 292 50.783%

문제

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

  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+XHViOWNjXHVjNTdkIFx1YmIzOFx1Yzc5MFx1YzVmNCBbU11cdWM2NDAgW1RdXHVhYzAwIFx1Yzg4Ylx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWI3N2NcdWJhNzQgXHVjNzc0XHViNGU0XHVjNzQ0IFx1YmQ5OVx1YzVlYyBcdWM0ZjQgW1NdW1RdIFx1YjYxMFx1ZDU1YyBcdWM4OGJcdWM3NDAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWI0NTAgXHVjODhiXHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNCBBXHVjNjQwIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjQgQVx1Yjk3YyAmIzM5O1x1Yzc3OFx1YzgxMVx1ZDU1YyBcdWI0NTAgXHViYjM4XHVjNzkwXHViOTdjIFx1YzExY1x1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQmIzM5OyBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVkMWI1XHVkNTc0IFx1YmIzOFx1Yzc5MFx1YzVmNCBCXHViODVjIFx1YmMxNFx1YWZiOFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIEFcdWI5N2MgQlx1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHVjOTExXHVjNWQwIFx1YjA5OFx1ZDBjMFx1YjA5OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWIzYzQgXHViYWE4XHViNDUwIFx1Yzg4Ylx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBBID0gYWFiYmFiYWIgXHVjNzc0XHVhY2UwIEIgPSBhYWFhYmJiYlx1Yjc3YyBcdWQ1NzQgXHViY2Y0XHVjNzkwLiBcdWFkZjhcdWI4MDdcdWIyZTRcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCA1XHViYzg4XHVjNzU4IFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWQxYjVcdWQ1NzQgQVx1Yjk3YyBCXHViODVjIFx1YmNjMFx1ZDY1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5hYWJiYTx1PmJhPFwvdT5iICZyYXJyOyBhYWI8dT5iYTxcL3U+YWJiICZyYXJyOyBhYWJhPHU+YmE8XC91PmJiICZyYXJyOyBhYTx1PmJhPFwvdT5hYmJiICZyYXJyOyBhYWE8dT5iYTxcL3U+YmJiICZyYXJyOyBhYWFhYmJiYjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQsIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjNzkwXHVjNWY0IEEsIEJcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YmQ4NFx1YjlhY1x1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMgQVx1YzY0MCBCXHViMjk0IFx1Yzg4Ylx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWJhNzAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMiBcdWM3NzRcdWMwYzEgMTAwLDAwMCBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMsIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNCZuYnNwO1x1YmIzOFx1Yzc5MFx1YzVmNCBBXHViOTdjIFx1YmIzOFx1Yzc5MFx1YzVmNCBCXHViODVjIFx1YmNjMFx1ZDY1OFx1ZDU2MCBcdWI1NGMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QgXHViY2MwXHVkNjU4XHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjAgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwNDUzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RyaW5nIFRyYW5zZm9ybWF0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5BIHN0cmluZyBpcyBjYWxsZWQgdG8gYmUgd2VsbC1mb3JtZWQgaWYgaXQgY2FuIGJlIGdlbmVyYXRlZCBieSB0aGUgZm9sbG93aW5nIHJ1bGVzOjxcL3A+XHJcblxyXG48b2wgc3R5bGU9XCJsaXN0LXN0eWxlLXR5cGU6bG93ZXItYWxwaGFcIj5cclxuXHQ8bGk+PGNvZGU+YWI8XC9jb2RlPiBpcyBhIHdlbGwtZm9ybWVkIHN0cmluZy48XC9saT5cclxuXHQ8bGk+SWYgPGNvZGU+UzxcL2NvZGU+IGlzIGEgd2VsbC1mb3JtZWQgc3RyaW5nLCA8Y29kZT5hU2I8XC9jb2RlPiBpcyBhbHNvIHdlbGwtZm9ybWVkLjxcL2xpPlxyXG5cdDxsaT5JZiA8Y29kZT5TPFwvY29kZT4gYW5kIDxjb2RlPlQ8XC9jb2RlPiBhcmUgd2VsbC1mb3JtZWQgc3RyaW5ncywgPGNvZGU+U1Q8XC9jb2RlPiBpcyBhbHNvIHdlbGwtZm9ybWVkLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCA8Y29kZT5hYWJiYWJhYjxcL2NvZGU+LCA8Y29kZT5hYmFiYWJhYjxcL2NvZGU+LCBhbmQgPGNvZGU+YWFhYWJiYmI8XC9jb2RlPiBhcmUgd2VsbC1mb3JtZWQgc3RyaW5ncy48XC9wPlxyXG5cclxuPHA+Rm9yIHR3byB3ZWxsLWZvcm1lZCBzdHJpbmdzLCBBIGFuZCBCLCB3ZSB3YW50IHRvIHRyYW5zZm9ybSBBIGludG8gQiBieSBwZXJmb3JtaW5nIHN1Y2Nlc3NpdmVseSB0aGUgb3BlcmF0aW9uIG9mIGV4Y2hhbmdpbmcgYWRqYWNlbnQgY2hhcmFjdGVycy4gQWZ0ZXIgcGVyZm9ybWluZyBlYWNoIG9wZXJhdGlvbiwgdGhlIHN0cmluZyBzaG91bGQgYmUgd2VsbC1mb3JtZWQuIExldCBBID0gPGNvZGU+YWFiYmFiYWI8XC9jb2RlPiBhbmQgQiA9IDxjb2RlPmFhYWFiYmJiPFwvY29kZT4uIFRoZW4gQSBjYW4gYmUgdHJhbnNmb3JtZWQgaW50byBCIGJ5IGZpdmUgb3BlcmF0aW9ucyBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48cD48Y29kZT5hYWJiYTx1PmJhPFwvdT5iPFwvY29kZT4gJnJhcnI7IDxjb2RlPmFhYjx1PmJhPFwvdT5hYmI8XC9jb2RlPiAmcmFycjsgPGNvZGU+YWFiYTx1PmJhPFwvdT5iYjxcL2NvZGU+ICZyYXJyOyA8Y29kZT5hYTx1PmJhPFwvdT5hYmJiPFwvY29kZT4gJnJhcnI7IDxjb2RlPmFhYTx1PmJhPFwvdT5iYmI8XC9jb2RlPiAmcmFycjsgPGNvZGU+YWFhYWJiYmI8XC9jb2RlPi48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdHdvIHdlbGwtZm9ybWVkIHN0cmluZ3MsIEEgYW5kIEIsIHlvdSBoYXZlIHRvIGZpbmQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG9wZXJhdGlvbnMgd2hpY2ggYXJlIG5lZWRlZCBmb3IgdHJhbnNmb3JtaW5nIEEgaW50byBCLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBhIGxpbmUgY29udGFpbmluZyB0d28gd2VsbC1mb3JtZWQgc3RyaW5ncyBBIGFuZCBCIHdoaWNoIGFyZSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIFRoZSBsZW5ndGggb2YgQSBpcyB0aGUgc2FtZSBhcyB0aGUgbGVuZ3RoIG9mIEIsIGFuZCBpcyBhdCBsZWFzdCAyIGFuZCBhdCBtb3N0IDEwMCwwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIHRoZSBtaW5pbXVtIG51bWJlciBvZiB0aGUgb3BlcmF0aW9ucyB3aGljaCBhcmUgbmVlZGVkIGZvciB0cmFuc2Zvcm1pbmcgQSBpbnRvIEIuIElmIHRoZSB0cmFuc2Zvcm1hdGlvbiBpcyBpbXBvc3NpYmxlLCBwcmludCAtMS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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