문제
영문 대문자로 이루어진 어떤 문자열을 이등분하여 2개의 문자열로 나누었을 때, 그 2개의 문자열이 같거나 어느 하나를 뒤집었을때 같아진다면 원래의 문자열을 twins문자열이라 한다. 예를 들어 “AAAA”나 “XYZXYZ”, “ABCDDCBA"와 같은 문자열은 twins문자열이지만 “AAAAA”나 “XYZYZ”, “ABCDCBA"와 같은 문자열은 twins문자열이 아니다. twins문자열이 아니라면 아래와 같은 작업을 통해 twins문자열로 만들 수 있다.
1. 문자열에서 한 개의 문자를 삭제한다. 2. 문자열의 임의의 위치에 한 개의 문자를 삽입한다. (맨 앞이나 맨 뒤에도 가능하다.) 3. 문자열에서 한 개의 문자를 다른 문자로 바꾼다.
예를 들어 문자열 "ABCAB"의 경우 세 번째 'C'를 삭제하여 'ABAB'로 만들거나, 맨 끝에 'C'를 삽입하여 "ABCABC"로 만들면 한번의 작업으로 twins문자열이 된다. 문자열 "ABACCA"는 두 번째 'B'와 세 번째 'A'를 삭제하여 'ACCA'로 만들거나, 문자열 뒷부분에 ‘B' 와 'A'를 삽입하여 "ABACCABA"로 만들거나 두 번째 'B'를 'C'로 또는 다섯 번째 'C'를 'B'로 바꾸고 세 번째 'A'를 'C'로 또는 네 번째 'C'를 'A'로 바꾸어 "ACCCCA", "ACAACA", "ABCCBA", "ABAABA"로 각각 만들 수 있으며, 이 경우 모두 두 번의 작업으로 twins문자열이 된 것이다.
한 개의 문자열을 입력받아 최소의 작업으로 twins문자열을 만드는 프로그램을 작성한 후, 그 작업횟수와 만들어진 twins문자열을 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에 영문 대문자로 이루어진 길이 3이상 100이하의 문자열이 주어진다. <제약조건> 전체 데이터의 30%는 문자열의 길이가 10이하이다.
출력
첫 번째 줄에 입력받은 문자열을 twins문자열로 만들기 위해 필요한 최소의 작업횟수를 출력하고, 두 번째 줄에 새로 만들어진 twins문자열을 출력한다.
만약 같은 작업횟수로 만들어진 문자열이 여러개일 경우에는 그 중 한 가지만 출력하면 된다.
예제
ABACCA
2
ABAABA
로그인해야 코드를 작성할 수 있어요.