邮递员投递问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给出一系列的街道(给出交叉点),请你编写一个程序计算至少遍历每条街一次的最小路程。遍历的路线必须开始和结束在同一个交叉点,这个交叉点是任意的。

在真实生活中,邮递员把车停在一个路口,然后步行所有的投递街道去投递邮件。走完一条街道的花费是该街道长度的函数。

Input

输入数据由一系列街道名字组成,一行一个街道名。

街道名字的第一个和最后一个字母定义了该街道的两个交叉点,街道名字的长度代表了走完该街道的花费。所有的街道名字由小写字母组成,长度不超过20。在邮递路线的最后,有一行字符串“deadend”,它不是街道的名字,而是结束标志。

例如,名为foo的街道的长度为3,它的两个交叉点为f和o;名为computer的街道的两个交叉点为c和r,其长度为8。任何一条街道的开头和结尾字母不会相同,而且任意两条街道的开头和结尾字母都不会相同。例如,如果有了街道foo,则不会再出现f…o或o…f的街道。任何街道都直接和两个交叉点相连。每一个邮递路线都有一条路径连接了所有的交叉点。

Output

第一行输出至少访问每条街道一次的最小花费。

第二行输出一条最小花费的邮递路线。只输出交叉点的字母,每个字母中间用一个空格隔开。

Sample Input

one
two
three
deadend

Sample Output

11
o e t o

Hint

Source