1. 

/**
* FWP: Ausgewaehlte Probleme aus dem ACM (SS10)
*
* Method: Dynamic Programming
* Problem: 10453 - MakePalindrome
* Accepted: 1.212
* @author Evgeni Pavlidis
*
*/
import java.io.*;
import java.util.*;

class Main {

private static int[][] f;
private static String input;

private static int calc(String s)
{
f = new int[s.length()+1][s.length()+1];
for(int k = 2; k <= s.length(); k++)
for(int i = 0; i <= s.length() - k; i++)
if(s.charAt(i) == s.charAt(i+k-1))
f[k][i] = f[k-2][i+1];
else
f[k][i] = Math.min(f[k-1][i], f[k-1][i+1]) + 1;

return f[s.length()][0];
}

private static String createPalindrome(int k, int i)
{
if(k == 0)
return "";

if(k == 1)
return "" + input.charAt(i);

char first = input.charAt(i);
char last = input.charAt(i+k-1);;

if(first == last)
return first + createPalindrome(k-2,i+1) + first;

if(f[k-1][i] > f[k-1][i+1])
return first + createPalindrome(k-1,i+1) + first;
else
return last + createPalindrome(k-1,i) + last;

}

public static void main(String... args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String palindrome;
int palindromeLength;

while( (input = reader.readLine()) != null )
{
input.trim();
palindromeLength = calc(input);
palindrome = createPalindrome(input.length(), 0);

System.out.println((palindromeLength) + " " + palindrome);

}
}
}