행맨 게임

주연이는 행맨 게임을 하고 있다. 이 게임에서는 숨겨진 단어에 들어 있는 알파벳을 모두 맞히면 된다.

처음에는 단어의 모든 알파벳이 -로 가려져 있다. 주연이가 알파벳 하나를 고르면, 그 알파벳이 단어에 포함되어 있을 때 해당하는 모든 위치가 드러난다. 단어에 들어 있는 모든 알파벳을 맞히면 게임이 끝난다.

주연이는 단어의 길이와 공백 위치만 보고도 어떤 단어인지 알 수 있다. 따라서 단어에 등장하는 서로 다른 알파벳을 어떤 순서로 고를지만 정하면 된다. 주연이는 버튼을 가능한 한 적게 눌러 게임을 끝내고 싶다.

알파벳을 고르기 위해 LEFT, RIGHT, OK 세 버튼을 사용한다.

• 화면에는 항상 알파벳 하나가 표시된다. 처음 표시되는 알파벳은 A이다.
• OK 버튼을 누르면 화면에 표시된 알파벳을 고른다. 숨겨진 단어에서 이 알파벳과 같은 모든 위치가 드러난다. 화면에 표시된 알파벳은 바뀌지 않는다.
• LEFT 버튼을 누르면 화면의 알파벳이 이전 알파벳으로 바뀐다. 예를 들어 C는 B가 되고, A는 Z가 된다.
• RIGHT 버튼을 누르면 화면의 알파벳이 다음 알파벳으로 바뀐다. 예를 들어 B는 C가 되고, Z는 A가 된다.

버튼을 누르는 횟수가 최소가 되도록 게임을 끝내는 방법을 찾아라. 그 방법에서 알파벳이 드러나는 순서를 출력한다. 정답이 여러 가지이면 아무거나 출력해도 된다.

첫 줄에 숨겨진 단어가 주어진다. 단어의 길이는 1 이상 100 이하이고, 알파벳 대문자와 공백으로만 이루어진다. 단어의 양 끝은 공백이 아니며, 단어 사이의 공백은 한 칸이다.

첫 줄에 게임을 끝내기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다.

둘째 줄에는 그 최소 횟수로 버튼을 눌렀을 때 알파벳이 드러나는 순서를 출력한다.

버튼 횟수에는 알파벳 사이를 이동하는 LEFT/RIGHT 횟수와 알파벳을 선택하는 OK 횟수가 모두 포함된다. 같은 알파벳이 여러 번 등장해도 한 번만 선택하면 그 위치가 모두 드러난다.