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

문제

육각 퍼즐이란 정육각형의 꼭지점과 중심에 원이 그려져 있는 퍼즐이고, 아래 그림과 같이 원이 연결되어 있다. 또, A, B, C, D, E, F로 글자가 새겨져 있는 동전이 아래 그림과 같이 원 위에 놓여 있다. 퍼즐에서 한 번 움직일 때, 동전을 연결된 빈 칸으로 움직일 수 있다.

처음 동전이 섞인 상태로 주어졌을 때, 동전을 아래 그림과 같이 맞추는 최소 이동 회수를 구하는 프로그램을 작성하시오. 처음 상태에서 가운데 칸은 비어있다.

처음 중심 정점은 비어있고 바깥쪽 정점 6 개가 A부터 F의 주어진 순열이 주어졌을 때 원래 ABCDEF 순서로 돌아가게 퍼즐을 푸려고 한다.

퍼즐의 상태는 위의 그림의 A 위치에 있는 동전부터 F까지 차례대로 주어진다. 퍼즐을 움직인 방법을 출력할 때는, 움직인 동전을 출력하면 된다.

예를 들어, FACDBE 퍼즐을 풀 때는 BEFAB로 움직이면 풀 수 있다.

퍼즐의 초기 상태가 주어졌을 때, 이 퍼즐을 푸는 방법을 출력하는 프로그램을 작성하시오. 이 때, 움직인 동전의 수를 최소로 해야 한다.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 퍼즐의 초기 상태가 주어진다.

출력

각 테스트 케이스에 대해서 최소 회수를 출력하고 공백을 출력한 뒤, 푸는 방법을 출력한다. 만약, 풀 수 없는 퍼즐이라면 -1을 출력한다.

예제 입력 1

12
FACDBE
ABCDEF
ADCEFB
ADCEBF
FEDCBA
FEDCAB
ECBFAD
ECBFDA
DCEBFA
DCEBAF
CBEADF
BDEAFC

예제 출력 1

5 BEFAB
0 
19 DABFECABFEDBACDEFAB
-1
29 EDCBEDFAEDFAEDBCAFBDEFACDEFAB
-1
19 CBFACBFACDEFACDEFAB
-1
13 CDAFBEDCBEDCB
-1
21 DAEBDAEBDCFEBDCABEFAB
16 FAEDBCAFBCAFEDCB
W3sicHJvYmxlbV9pZCI6IjI3MDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MjFcdWFjMDEgXHVkMzdjXHVjOTkwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM3MjFcdWFjMDEgXHVkMzdjXHVjOTkwXHVjNzc0XHViNzgwIFx1YzgxNVx1YzcyMVx1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFmMmRcdWM5YzBcdWM4MTBcdWFjZmMgXHVjOTExXHVjMmVjXHVjNWQwIFx1YzZkMFx1Yzc3NCBcdWFkZjhcdWI4MjRcdWM4MzggXHVjNzg4XHViMjk0IFx1ZDM3Y1x1Yzk5MFx1Yzc3NFx1YWNlMCwgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjNmQwXHVjNzc0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgQSwgQiwgQywgRCwgRSwgRlx1Yjg1YyBcdWFlMDBcdWM3OTBcdWFjMDAgXHVjMGM4XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWIzZDlcdWM4MDRcdWM3NzQgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjNmQwIFx1YzcwNFx1YzVkMCBcdWIxOTNcdWM1ZWMgXHVjNzg4XHViMmU0LiBcdWQzN2NcdWM5OTBcdWM1ZDBcdWMxMWMgXHVkNTVjIFx1YmM4OCBcdWM2YzBcdWM5YzFcdWM3N2MgXHViNTRjLCBcdWIzZDlcdWM4MDRcdWM3NDQgXHVjNWYwXHVhY2IwXHViNDFjIFx1YmU0OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Y2M5OFx1Yzc0YyBcdWIzZDlcdWM4MDRcdWM3NzQgXHVjMTFlXHVjNzc4IFx1YzBjMVx1ZDBkY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWIzZDlcdWM4MDRcdWM3NDQgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViOWRlXHVjZDk0XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWM3NzRcdWIzZDkgXHVkNjhjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWNjOThcdWM3NGMgXHVjMGMxXHVkMGRjXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzZiNFx1YjM3MCBcdWNlNzhcdWM3NDAgXHViZTQ0XHVjNWI0XHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RoZXRhMS5wbmdcIiBzdHlsZT1cIndpZHRoOiAyOTFweDsgaGVpZ2h0OiAyMjlweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjYzk4XHVjNzRjIFx1YzkxMVx1YzJlYyBcdWM4MTVcdWM4MTBcdWM3NDAgXHViZTQ0XHVjNWI0XHVjNzg4XHVhY2UwIFx1YmMxNFx1YWU2NVx1Y2FiZCBcdWM4MTVcdWM4MTAgNiBcdWFjMWNcdWFjMDAgQVx1YmQ4MFx1ZDEzMCBGXHVjNzU4IFx1YzhmY1x1YzViNFx1YzljNCBcdWMyMWNcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YyBcdWM2ZDBcdWI3OTggQUJDREVGIFx1YzIxY1x1YzExY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWFjMDBcdWFjOGMgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1ZDQ3OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDM3Y1x1Yzk5MFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWIyOTQgXHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc1OCBBIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViM2Q5XHVjODA0XHViZDgwXHVkMTMwIEZcdWFlNGNcdWM5YzAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMzdjXHVjOTkwXHVjNzQ0IFx1YzZjMFx1YzljMVx1Yzc3OCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjZDljXHViODI1XHVkNTYwIFx1YjU0Y1x1YjI5NCwgXHVjNmMwXHVjOWMxXHVjNzc4IFx1YjNkOVx1YzgwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBGQUNEQkUgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1ZDQ4MCBcdWI1NGNcdWIyOTQgQkVGQUJcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHViYTc0IFx1ZDQ4MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RoZXRhMi5wbmdcIiBzdHlsZT1cIndpZHRoOiA1OTNweDsgaGVpZ2h0OiAxMDVweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkMzdjXHVjOTkwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1ZDM3Y1x1Yzk5MFx1Yzc0NCBcdWQ0NzhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM3NzQgXHViNTRjLCBcdWM2YzBcdWM5YzFcdWM3NzggXHViM2Q5XHVjODA0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQoMSAmbGU7IFQgJmxlOyAxMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVkMzdjXHVjOTkwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWNkNWNcdWMxOGMgXHVkNjhjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjIFx1YjRhNCwgXHVkNDc4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVkNDgwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVkMzdjXHVjOTkwXHVjNzc0XHViNzdjXHViYTc0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzAxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhldGEgUHV6emxlIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgVGhldGEgUHV6emxlIGNvbnNpc3RzIG9mIGEgYmFzZSB3aXRoIDYgcG9zaXRpb25zIGF0IHRoZSB2ZXJ0aWNlcyBvZiBhIHJlZ3VsYXIgaGV4YWdvbiBhbmQgYW5vdGhlciBwb3NpdGlvbiBhdCB0aGUgY2VudGVyLCBjb25uZWN0ZWQgYXMgc2hvd24gaW4gdGhlIGZpZ3VyZSBiZWxvdy4gVGhlcmUgYXJlIHNpeCB0b2tlbnMgbGFiZWxlZCBBLCBCLCBDLCBELCBFIGFuZCBGLiBBIHNpbmdsZSBtb3ZlIG9mIHRoZSBwdXp6bGUgaXMgdG8gbW92ZSBhIHRva2VuIHRvIGFuIGFkamFjZW50IGVtcHR5IHBvc2l0aW9uIChhbG9uZyBhbiBhbGxvd2VkIGNvbm5lY3Rpb24gJm5kYXNoOyB0aGUgbGluZSBzZWdtZW50cyBpbiB0aGUgZGlhZ3JhbSBiZWxvdykuIFRoZSBpZGVhIG9mIHRoZSBwdXp6bGUgaXMgdG8gc3RhcnQgd2l0aCBhbiBpbml0aWFsIGFycmFuZ2VtZW50IG9mIHRva2VucyB3aXRoIHRoZSBjZW50ZXIgZW1wdHkgYW5kLCBieSBhIHNlcXVlbmNlIG9mIG1vdmVzLCBnZXQgdG8gdGhlIGNvbmZpZ3VyYXRpb24gaW4gdGhlIGZpZ3VyZSBiZWxvdy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90aGV0YTEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI5cHg7IHdpZHRoOjI5MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkFuIGluaXRpYWwgcG9zaXRpb24gZm9yIHRoZSBwdXp6bGUgaXMgZ2l2ZW4gYnkgYSBwZXJtdXRhdGlvbiBvZiB0aGUgbGV0dGVycyBBIHRocm91Z2ggRi4gVGhlIGZpcnN0IGxldHRlciBzdGFydHMgYXQgQSBpbiB0aGUgZmlndXJlLCB0aGUgbmV4dCBhdCBCIGFuZCBzbyBvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBzZXF1ZW5jZSBvZiBtb3ZlcyBpcyBzcGVjaWZpZWQgYnkgbGlzdGluZyB0aGUgbGFiZWxzIG9mIHRva2VucyB0byBiZSBtb3ZlZCwgaW4gdGhlIG9yZGVyIHRoZXkgYXJlIHRvIGJlIG1vdmVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgdG8gc29sdmUgdGhlIHB1enpsZSBGQUNEQkUsIHVzZSB0aGUgbW92ZXMgQkVGQUIuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdGhldGEyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEwNXB4OyB3aWR0aDo1OTNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Ob3RlOiBOb3QgYWxsIHN0YXJ0aW5nIHBlcm11dGF0aW9ucyBjYW4gYmUgc29sdmVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gd2hpY2gsIGdpdmVuIGFuIGluaXRpYWwgcGVybXV0YXRpb24sIGVpdGhlciBmaW5kcyB0aGUgc2hvcnRlc3Qgc2VxdWVuY2Ugb2YgbW92ZXMgdG8gc29sdmUgdGhlIHB1enpsZSBvciBkZXRlcm1pbmVzIHRoYXQgdGhlcmUgaXMgbm8gc29sdXRpb24uJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFAsICgxICZsZTsgUCAmbGU7IDEwMDApLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0aGF0IGZvbGxvdy4gRWFjaCBkYXRhIHNldCBpcyBhIHNpbmdsZSBsaW5lIHRoYXQgY29udGFpbnMgdGhlIGRhdGEgc2V0IG51bWJlciwgZm9sbG93ZWQgYnkgYSBzcGFjZSwgZm9sbG93ZWQgYnkgYSBwZXJtdXRhdGlvbiBvZiB0aGUgbGV0dGVycyBBIHRocm91Z2ggRiBnaXZpbmcgdGhlIGluaXRpYWwgcHV6emxlIHBvc2l0aW9uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0IHRoZXJlIGlzIGEgc2luZ2xlIGxpbmUgb2Ygb3V0cHV0LiBJZiB0aGVyZSBpcyBubyBzb2x1dGlvbiwgdGhlIGxpbmUgY29udGFpbnMgYSBkZWNpbWFsIGludGVnZXIgZ2l2aW5nIHRoZSBkYXRhIHNldCBudW1iZXIgZm9sbG93ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIGZvbGxvd2VkIGJ5IHRoZSBzdHJpbmcgTk8gU09MVVRJT04uIElmIHRoZXJlIGlzIGEgc29sdXRpb24sIHRoZSBsaW5lIGNvbnRhaW5zIGEgZGVjaW1hbCBpbnRlZ2VyIGdpdmluZyB0aGUgZGF0YSBzZXQgbnVtYmVyIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlLCBmb2xsb3dlZCBieSB0aGUgbnVtYmVyIG9mIG1vdmVzIGluIHRoZSBzb2x1dGlvbiwgZm9sbG93ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIGZvbGxvd2VkIGJ5IHRoZSBzb2x1dGlvbiBhcyBhIHN0cmluZyBvZiB0aGUgbGV0dGVycyBBIHRocm91Z2ggRi4gSWYgdGhlIG51bWJlciBvZiBtb3ZlcyBpcyB6ZXJvICgwKSwgeW91IHNob3VsZCBzdGlsbCBvdXRwdXQgdGhlIHNwYWNlIGFmdGVyIHRoZSAwLCBldmVuIHRob3VnaCB0aGVyZSBpcyBubyBzdHJpbmcgb2YgbGV0dGVycy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=