描述

图算法是计算机科学中的一个重要部分，其历史可以追溯到欧拉和著名的柯尼斯堡七桥问题。许多优化问题涉及确定有效的方法来推理图。

这个问题涉及为邮递员确定一条路线，使得所有邮件都能够送达，同时邮递员行走的距离最小，以便让疲惫的双腿得到休息。

给定一系列街道（连接给定的交叉口），你需要编写一个程序，确定一条最小费用的旅行路线，这条路线必须至少经过每条街道一次，并且旅行必须从同一个交叉口开始并结束。

“现实生活”的类比是，邮递员将卡车停在一个交叉口，然后走遍所有街道（送邮件），并返回卡车继续下一条路线。

穿越一条街道的费用是街道长度的一个函数（即使没有送邮件，走路也会有费用）。

在这个问题中，连接到一个交叉口的街道数量称为交叉口的度。最多只有两个交叉口具有奇数度。其他所有交叉口的度数都是偶数，即该交叉口与偶数条街道相连。

输入

输入由一个或多个邮递路线组成。每条路线由一系列街道名称（字符串）组成，每条街道占一行，并以字符串$“deadend”$结束，该字符串不属于路线的一部分。每个街道名称的第一个和最后一个字母指定该街道的两个交叉口，街道名称的长度表示穿越该街道的费用。所有街道名称将由小写字母组成。

例如，名称 $`foo`$ 表示一条连接交叉口 $f$ 和 $o$ 的街道，长度为 $3$；名称 $`computer`$ 表示一条连接交叉口 $c$ 和 $r$ 的街道，长度为 $8$。没有两条街道直接连接相同的两个交叉口，并且每对交叉口最多只有一条直接连接的街道。如题目所示，每条邮递路线中的奇数度交叉口最多只有两个。在每条邮递路线中，所有交叉口之间都有路径连接，也就是说，交叉口是连通的。

输出

对于每条邮递路线，输出应该包含最小旅行费用，即最小的费用使得路线遍历所有街道至少一次。最小旅行费用应按照输入邮递路线的顺序输出。

one
two
three
deadend
mit
dartmouth
linkoping
tasmania
york
emory
cornell
duke
kaunas
hildesheim
concord
arkansas
williams
glasgow
deadend

11
114

来源

Duke Internet Programming Contest 1992, UVA 117