文件读写

• 输入文件 sign.in
• 输出文件 sign.out

限制

• 1000ms
• 512MB

题目描述

程老师在南昌老街盘下一间文具店，准备开业。他亲手设计了一串小写英文字母，打算做成发光招牌挂在门头上。

老师傅看了一眼设计稿，摇摇头说："小伙子，招牌上的字讲究个吉利——正着念和反着念得一模一样。你看人家'来来回回'，正念反念都是'来来回回'，这才叫顺。"

程老师仔细端详自己那串字母，发现正反念确实不一样。但他灵机一动，问老师傅："如果我从这串字母里删掉几个字母——剩下的字母保持原来的先后顺序——让剩下的串正着念反着念都一样，您看行不行？"

老师傅虽然觉得这办法有点取巧，但还是同意了。程老师现在面对两个现实问题：第一，为了省料，他最少要删掉多少个字母？第二，如果删最少字母的方案不止一种，最后挂在门头上的字母串应该是字典序最小的那个——毕竟字母越靠前，看着越顺眼。

输入格式

一行一个字符串 $s$，全部由小写英文字母组成，表示程老师设计的原始字母串。

输出格式

第一行一个整数，表示最少需要删掉的字母个数。

第二行一个字符串，表示删完后得到的回文字母串。如果存在多种删法能得到同样长的回文，输出字典序最小的那个。

数据范围

• 特殊性质 A：字符串中所有字母都相同。此时删掉 $0$ 个字母，原串已是回文。
• 特殊性质 B：原串本身就是回文。此时删掉 $0$ 个字母，直接输出原串。

对于 $100\%$ 的数据，$1 \leq \lvert s \rvert \leq 300$，字符串仅包含小写英文字母。

abca

1
aba

样例 1 解释

原始字母串 abca 正念是 abca，反念是 acba，两者不同，必须删字母。

删掉 c 保留第 $1, 2, 4$ 个字母得到 aba，删掉 b 保留第 $1, 3, 4$ 个字母得到 aca，两种方案都只删 $1$ 个字母。二者第一个字母均为 a，第二个字母 b < c，故输出 aba。

abcba

0
abcba

ab

1
a