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

문제

육각 퍼즐이란 정육각형의 꼭짓점과 중심에 원이 그려져 있는 퍼즐이고, 아래 그림과 같이 원이 연결되어 있다. 또, 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
W3sicHJvYmxlbV9pZCI6IjI3MDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MjFcdWFjMDEgXHVkMzdjXHVjOTkwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM3MjFcdWFjMDEgXHVkMzdjXHVjOTkwXHVjNzc0XHViNzgwIFx1YzgxNVx1YzcyMVx1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWFjZmMgXHVjOTExXHVjMmVjXHVjNWQwIFx1YzZkMFx1Yzc3NCBcdWFkZjhcdWI4MjRcdWM4MzggXHVjNzg4XHViMjk0IFx1ZDM3Y1x1Yzk5MFx1Yzc3NFx1YWNlMCwgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjNmQwXHVjNzc0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgQSwgQiwgQywgRCwgRSwgRlx1Yjg1YyBcdWFlMDBcdWM3OTBcdWFjMDAgXHVjMGM4XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWIzZDlcdWM4MDRcdWM3NzQgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjNmQwIFx1YzcwNFx1YzVkMCBcdWIxOTNcdWM1ZWMgXHVjNzg4XHViMmU0LiBcdWQzN2NcdWM5OTBcdWM1ZDBcdWMxMWMgXHVkNTVjIFx1YmM4OCBcdWM2YzBcdWM5YzFcdWM3N2MgXHViNTRjLCBcdWIzZDlcdWM4MDRcdWM3NDQgXHVjNWYwXHVhY2IwXHViNDFjIFx1YmU0OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Y2M5OFx1Yzc0YyBcdWIzZDlcdWM4MDRcdWM3NzQgXHVjMTFlXHVjNzc4IFx1YzBjMVx1ZDBkY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWIzZDlcdWM4MDRcdWM3NDQgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViOWRlXHVjZDk0XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWM3NzRcdWIzZDkgXHVkNjhjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWNjOThcdWM3NGMgXHVjMGMxXHVkMGRjXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzZiNFx1YjM3MCBcdWNlNzhcdWM3NDAgXHViZTQ0XHVjNWI0XHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RoZXRhMS5wbmdcIiBzdHlsZT1cIndpZHRoOiAyOTFweDsgaGVpZ2h0OiAyMjlweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjYzk4XHVjNzRjIFx1YzkxMVx1YzJlYyBcdWM4MTVcdWM4MTBcdWM3NDAgXHViZTQ0XHVjNWI0XHVjNzg4XHVhY2UwIFx1YmMxNFx1YWU2NVx1Y2FiZCBcdWM4MTVcdWM4MTAgNiBcdWFjMWNcdWFjMDAgQVx1YmQ4MFx1ZDEzMCBGXHVjNzU4IFx1YzhmY1x1YzViNFx1YzljNCBcdWMyMWNcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YyBcdWM2ZDBcdWI3OTggQUJDREVGIFx1YzIxY1x1YzExY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWFjMDBcdWFjOGMgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1ZDQ3OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDM3Y1x1Yzk5MFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWIyOTQgXHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc1OCBBIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViM2Q5XHVjODA0XHViZDgwXHVkMTMwIEZcdWFlNGNcdWM5YzAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMzdjXHVjOTkwXHVjNzQ0IFx1YzZjMFx1YzljMVx1Yzc3OCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjZDljXHViODI1XHVkNTYwIFx1YjU0Y1x1YjI5NCwgXHVjNmMwXHVjOWMxXHVjNzc4IFx1YjNkOVx1YzgwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBGQUNEQkUgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1ZDQ4MCBcdWI1NGNcdWIyOTQgQkVGQUJcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHViYTc0IFx1ZDQ4MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RoZXRhMi5wbmdcIiBzdHlsZT1cIndpZHRoOiA1OTNweDsgaGVpZ2h0OiAxMDVweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkMzdjXHVjOTkwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1ZDM3Y1x1Yzk5MFx1Yzc0NCBcdWQ0NzhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM3NzRcdWI1NGMsIFx1YzZjMFx1YzljMVx1Yzc3OCBcdWIzZDlcdWM4MDRcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCgxICZsZTsgVCAmbGU7IDEwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWQzN2NcdWM5OTBcdWM3NTggXHVjZDA4XHVhZTMwIFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1Y2Q1Y1x1YzE4YyBcdWQ2OGNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHViNGE0LCBcdWQ0NzhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWQ0ODAgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWQzN2NcdWM5OTBcdWM3NzRcdWI3N2NcdWJhNzQgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI3MDEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGV0YSBQdXp6bGUiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBUaGV0YSBQdXp6bGUgY29uc2lzdHMgb2YgYSBiYXNlIHdpdGggNiBwb3NpdGlvbnMgYXQgdGhlIHZlcnRpY2VzIG9mIGEgcmVndWxhciBoZXhhZ29uIGFuZCBhbm90aGVyIHBvc2l0aW9uIGF0IHRoZSBjZW50ZXIsIGNvbm5lY3RlZCBhcyBzaG93biBpbiB0aGUgZmlndXJlIGJlbG93LiBUaGVyZSBhcmUgc2l4IHRva2VucyBsYWJlbGVkIEEsIEIsIEMsIEQsIEUgYW5kIEYuIEEgc2luZ2xlIG1vdmUgb2YgdGhlIHB1enpsZSBpcyB0byBtb3ZlIGEgdG9rZW4gdG8gYW4gYWRqYWNlbnQgZW1wdHkgcG9zaXRpb24gKGFsb25nIGFuIGFsbG93ZWQgY29ubmVjdGlvbiAmbmRhc2g7IHRoZSBsaW5lIHNlZ21lbnRzIGluIHRoZSBkaWFncmFtIGJlbG93KS4gVGhlIGlkZWEgb2YgdGhlIHB1enpsZSBpcyB0byBzdGFydCB3aXRoIGFuIGluaXRpYWwgYXJyYW5nZW1lbnQgb2YgdG9rZW5zIHdpdGggdGhlIGNlbnRlciBlbXB0eSBhbmQsIGJ5IGEgc2VxdWVuY2Ugb2YgbW92ZXMsIGdldCB0byB0aGUgY29uZmlndXJhdGlvbiBpbiB0aGUgZmlndXJlIGJlbG93LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RoZXRhMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjlweDsgd2lkdGg6MjkxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QW4gaW5pdGlhbCBwb3NpdGlvbiBmb3IgdGhlIHB1enpsZSBpcyBnaXZlbiBieSBhIHBlcm11dGF0aW9uIG9mIHRoZSBsZXR0ZXJzIEEgdGhyb3VnaCBGLiBUaGUgZmlyc3QgbGV0dGVyIHN0YXJ0cyBhdCBBIGluIHRoZSBmaWd1cmUsIHRoZSBuZXh0IGF0IEIgYW5kIHNvIG9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIHNlcXVlbmNlIG9mIG1vdmVzIGlzIHNwZWNpZmllZCBieSBsaXN0aW5nIHRoZSBsYWJlbHMgb2YgdG9rZW5zIHRvIGJlIG1vdmVkLCBpbiB0aGUgb3JkZXIgdGhleSBhcmUgdG8gYmUgbW92ZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB0byBzb2x2ZSB0aGUgcHV6emxlIEZBQ0RCRSwgdXNlIHRoZSBtb3ZlcyBCRUZBQi48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90aGV0YTIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTA1cHg7IHdpZHRoOjU5M3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk5vdGU6IE5vdCBhbGwgc3RhcnRpbmcgcGVybXV0YXRpb25zIGNhbiBiZSBzb2x2ZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCwgZ2l2ZW4gYW4gaW5pdGlhbCBwZXJtdXRhdGlvbiwgZWl0aGVyIGZpbmRzIHRoZSBzaG9ydGVzdCBzZXF1ZW5jZSBvZiBtb3ZlcyB0byBzb2x2ZSB0aGUgcHV6emxlIG9yIGRldGVybWluZXMgdGhhdCB0aGVyZSBpcyBubyBzb2x1dGlvbi4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKDEgJmxlOyBQICZsZTsgMTAwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzIHRoYXQgZm9sbG93LiBFYWNoIGRhdGEgc2V0IGlzIGEgc2luZ2xlIGxpbmUgdGhhdCBjb250YWlucyBhIHBlcm11dGF0aW9uIG9mIHRoZSBsZXR0ZXJzIEEgdGhyb3VnaCBGIGdpdmluZyB0aGUgaW5pdGlhbCBwdXp6bGUgcG9zaXRpb24uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQgdGhlcmUgaXMgYSBzaW5nbGUgbGluZSBvZiBvdXRwdXQuIElmIHRoZXJlIGlzIG5vIHNvbHV0aW9uLCB0aGUgbGluZSBjb250YWlucyB0aGUgc3RyaW5nIE5PIFNPTFVUSU9OLiBJZiB0aGVyZSBpcyBhIHNvbHV0aW9uLCB0aGUgbGluZSBjb250YWlucyBhIGRlY2ltYWwgaW50ZWdlciBnaXZpbmcgdGhlIG51bWJlciBvZiBtb3ZlcyBpbiB0aGUgc29sdXRpb24sIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlLCBmb2xsb3dlZCBieSB0aGUgc29sdXRpb24gYXMgYSBzdHJpbmcgb2YgdGhlIGxldHRlcnMgQSB0aHJvdWdoIEYuIElmIHRoZSBudW1iZXIgb2YgbW92ZXMgaXMgemVybyAoMCksIHlvdSBzaG91bGQgc3RpbGwgb3V0cHV0IHRoZSBzcGFjZSBhZnRlciB0aGUgMCwgZXZlbiB0aG91Z2ggdGhlcmUgaXMgbm8gc3RyaW5nIG9mIGxldHRlcnMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==