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

문제

구슬 26개(회색 13개, 노란색 13개)가 오른쪽 그림과 같이 두 원에 놓여있다. 각각의 원에 있는 구슬은 시계방향이나 반시계방향으로 자유롭게 돌릴 수 있다.

위쪽 원과 아래쪽 원은 작은 원으로 연결되어 있다. 이 원은 항상 180도씩 돌릴 수 있으며, 위쪽 구슬 3개와 아럐쪽 구슬 3개의 위치를 서로 바꾼다.

상근이는 위에는 회색 구슬, 아래에는 노란색 구슬만 있게 만들고한다. 이 때, 가운데 원을 돌리는 회수의 최소값을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 각 원에 있는 조약돌의 색상이 주어진다. 모든 줄은 y 13개와 g 13개의 순열이다. 

각 줄의 처음 13개 문자는 위쪽 원에 있는 구슬의 색상을 시계방향으로 나타낸 것이고, 나머지는 아래쪽 원의 정보이다. y는 노란색, g는 회색을 나타낸다.

출력

각 테스트 케이스에 대해서, 위에는 회색 구슬, 아래에는 노란색 구슬만 넣을 때, 가운데 원을 돌리는 회수의 최소값을 출력한다.

예제 입력 1

gggggggggggggyyyyyyyyyyyyy
yyyyyggggggggyyyygggggyyyy
gyyygyggyyygyyggyyggggyygg
ygygygygygygygygygygygygyg

예제 출력 1

0
2
5
6
W3sicHJvYmxlbV9pZCI6IjQ1MDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkNmNcdWMyYWMiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbWJyLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDozNzRweDsgd2lkdGg6MjAwcHhcIiBcLz5cdWFkNmNcdWMyYWMgMjZcdWFjMWMoXHVkNjhjXHVjMGM5IDEzXHVhYzFjLCBcdWIxNzhcdWI3ODBcdWMwYzkgMTNcdWFjMWMpXHVhYzAwIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YjQ1MCBcdWM2ZDBcdWM1ZDAgXHViMTkzXHVjNWVjXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjNmQwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFkNmNcdWMyYWNcdWM3NDAgXHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjNzc0XHViMDk4IFx1YmMxOFx1YzJkY1x1YWNjNFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM3OTBcdWM3MjBcdWI4NmRcdWFjOGMgXHViM2NjXHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVjNzA0XHVjYWJkIFx1YzZkMFx1YWNmYyBcdWM1NDRcdWI3OThcdWNhYmQgXHVjNmQwXHVjNzQwIFx1Yzc5MVx1Yzc0MCBcdWM2ZDBcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YzZkMFx1Yzc0MCBcdWQ1NmRcdWMwYzEgMTgwXHViM2M0XHVjNTI5IFx1YjNjY1x1YjliNCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM3MDRcdWNhYmQgXHVhZDZjXHVjMmFjIDNcdWFjMWNcdWM2NDAgXHVjNTQ0XHViN2QwXHVjYWJkIFx1YWQ2Y1x1YzJhYyAzXHVhYzFjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWMxMWNcdWI4NWMgXHViYzE0XHVhZmJjXHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3MDRcdWM1ZDBcdWIyOTQgXHVkNjhjXHVjMGM5IFx1YWQ2Y1x1YzJhYywgXHVjNTQ0XHViNzk4XHVjNWQwXHViMjk0IFx1YjE3OFx1Yjc4MFx1YzBjOSBcdWFkNmNcdWMyYWNcdWI5Y2MgXHVjNzg4XHVhYzhjIFx1YjljY1x1YjRlNFx1YWNlMFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVhYzAwXHVjNmI0XHViMzcwIFx1YzZkMFx1Yzc0NCBcdWIzY2NcdWI5YWNcdWIyOTQgXHVkNjhjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHVjNmQwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM4NzBcdWM1N2RcdWIzY2NcdWM3NTggXHVjMGM5XHVjMGMxXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzkwNFx1Yzc0MCB5IDEzXHVhYzFjXHVjNjQwIGcgMTNcdWFjMWNcdWM3NTggXHVjMjFjXHVjNWY0XHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YWMwMSBcdWM5MDRcdWM3NTggXHVjYzk4XHVjNzRjIDEzXHVhYzFjIFx1YmIzOFx1Yzc5MFx1YjI5NCBcdWM3MDRcdWNhYmQgXHVjNmQwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFkNmNcdWMyYWNcdWM3NTggXHVjMGM5XHVjMGMxXHVjNzQ0IFx1YzJkY1x1YWNjNFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjggXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWIwOThcdWJhMzhcdWM5YzBcdWIyOTQgXHVjNTQ0XHViNzk4XHVjYWJkIFx1YzZkMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWM3NzRcdWIyZTQuIHlcdWIyOTQgXHViMTc4XHViNzgwXHVjMGM5LCBnXHViMjk0IFx1ZDY4Y1x1YzBjOVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM3MDRcdWM1ZDBcdWIyOTQgXHVkNjhjXHVjMGM5IFx1YWQ2Y1x1YzJhYywgXHVjNTQ0XHViNzk4XHVjNWQwXHViMjk0IFx1YjE3OFx1Yjc4MFx1YzBjOSBcdWFkNmNcdWMyYWNcdWI5Y2MgXHViMTIzXHVjNzQ0IFx1YjU0YywgXHVhYzAwXHVjNmI0XHViMzcwIFx1YzZkMFx1Yzc0NCBcdWIzY2NcdWI5YWNcdWIyOTQgXHVkNjhjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDUwMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJyaWRnZWQgTWFyYmxlIFJpbmdzICIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9tYnIucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjM3NHB4OyB3aWR0aDoyMDBweFwiIFwvPjI2IG1hcmJsZXMmbWRhc2g7aGFsZiB5ZWxsb3cgYW5kIGhhbGYgZ3JheSZtZGFzaDthcmUgZGlzdHJpYnV0ZWQgYmV0d2VlbiB0d28gY2lyY2xlcyBvZiAxMyBtYXJibGVzIGVhY2guIFRoZSBtYXJibGVzIGluIGVhY2ggY2lyY2xlIGNhbiBiZSBmcmVlbHkgcm90YXRlZCBjbG9ja3dpc2Ugb3IgY291bnRlcmNsb2Nrd2lzZS4gVGhlIHVwcGVyIGFuZCBsb3dlciBjaXJjbGVzIGFyZSBicmlkZ2VkIGJ5IGEgc21hbGxlciBjaXJjbGUsIHdoaWNoIHJvdGF0ZXMmbWRhc2g7aW4gdGhlIHBsYW5lIG9mIHRoZSBib2FyZCZtZGFzaDsxODAgZGVncmVlcywgZWZmZWN0aXZlbHkgZXhjaGFuZ2luZyB0aGUgdGhyZWUgYm90dG9tbW9zdCBtYXJibGVzIG9mIHRoZSB1cHBlciBjaXJjbGUgd2l0aCB0aGUgdGhyZWUgdXBwZXJtb3N0IG1hcmJsZXMgb2YgdGhlIGxvd2VyIG9uZS4gVGhlIGdvYWwgaXMgdG8gZ2V0IGFsbCBncmF5IG1hcmJsZXMgdG8gdGhlIHVwcGVyIGNpcmNsZSBhbmQgYWxsIHllbGxvdyBtYXJibGVzIHRvIHRoZSBsb3dlciBvbmUgd2hpbGUgbWluaW1pemluZyB0aGUgbnVtYmVyIG9mIHRpbWVzIHRoZSBicmlkZ2luZyBjaXJjbGUgaXMgcm90YXRlZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBpcyBhIHNlcmllcyBvZiBsaW5lcywgd2hlcmUgZWFjaCBsaW5lIGRlc2NyaWJlcyBhbiBpbml0aWFsIGJvYXJkIGNvbmZpZ3VyYXRpb24uIEVhY2ggbGluZSBpcyBhIHBlcm11dGF0aW9uIG9mIDEzIHkmcnNxdW87cyBhbmQgMTMgZyZyc3F1bztzLiBUaGUgZmlyc3QgaGFsZiBvZiB0aGUgbGluZSBkZXNjcmliZXMgdGhlIGNsb2Nrd2lzZSBjb25maWd1cmF0aW9uIG9mIHRoZSB1cHBlciBjaXJjbGUsIGFuZCB0aGUgcmVzdCBvZiB0aGUgbGluZSBkZXNjcmliZXMgdGhlIGNsb2Nrd2lzZSBjb25maWd1cmF0aW9uIG9mIHRoZSBsb3dlciBvbmUuIE9mIGNvdXJzZSwgZWFjaCB5IGNvcnJlc3BvbmRzIHRvIGEgeWVsbG93IG1hcmJsZSwgYW5kIGVhY2ggZyBjb3JyZXNwb25kcyB0byBhIGdyYXkgb25lLiBUaGUgaW5wdXQgZmlsZSB3aWxsIGluY2x1ZGUgbXVsdGlwbGUgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHNvbWUgcGVybXV0YXRpb24gb2YgdGhlIHN0cmluZyB5PHN1cD4xMzxcL3N1cD5nPHN1cD4xMzxcL3N1cD4uIEFsbCBsaW5lcyAoaW5jbHVkaW5nIHRoZSBsYXN0IG9uZSkgYXJlIHRlcm1pbmF0ZWQgd2l0aCBhIG5ld2xpbmUuIFRoZSBuZXdsaW5lIGltbWVkaWF0ZWx5IGZvbGxvd3MgdGhlIGxhc3QgbGV0dGVyIG9uIHRoZSBsaW5lLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGlucHV0IGNhc2UsIHlvdSBzaG91bGQgcHJpbnQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGJyaWRnZSByb3RhdGlvbnMgb24gYSBzaW5nbGUgbGluZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=