1. 

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
 * Problem: 117 - The Postal Worker Rings Once
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=53
 *
 * @author Philippe Brousse
 * @version 1.0, 10/23/2010
 *
 * Method : Ad-Hoc
 * Status : Accepted
 * Runtime: 0.112
 */
package postalworker;

import java.io.*;
import java.util.*;

/**
 *
 * @author Philippe Brousse
 * @version 1.0
 */
public class Main
{

    static Graph graph;

    /**
     * @param args
     */
    public static void main(String... args) throws IOException
    {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        do
        {
            //TODO: Andere Speichermöglichkeit verwenden
            //erste Straße einlesen
            String in = input.readLine().trim();
            LinkedList<String> strassen = new LinkedList<String>();
            graph = new Graph();

            //Alle weiteren Straßen einlesen
            do
            {
                //Strasse in die Strassenliste
                strassen.add(in);
                //Kreuzungen der Strasse
                char von = in.charAt(0);
                char nach = in.charAt(in.length() - 1);
                //Strasse an Kreuzung 1...
                if (!graph.contains(von))
                {
                    //System.out.println("Neuer Knoten: " + von);
                    graph.add(new Node(von));
                }
                //Kein Check: jede Strasse hat eine einzigartige Kombination
                //aus erstem und letztem Buchstaben!!!
                //an den Knoten 'von' den Knoten 'nach' samt Kosten anhängen
                //System.out.println("Hänge " + nach + " an " + von + " an");
                graph.get(von).add(nach, in.length());

                //...und 2 anhängen
                if (!graph.contains(nach))
                {
                    //System.out.println("Neuer Knoten: " + nach);

                    graph.add(new Node(nach));
                }
                //an den Knoten 'nach' den Knoten 'von' samt Kosten anhängen
                //System.out.println("Hänge " + von + " an " + nach + " an");

                graph.get(nach).add(von, in.length());

                //nächste Strasse
                in = input.readLine().trim();
            }
            //hier: wenn deadend gelesen -> Ende, String wird verworfen
            while (!in.equals("deadend"));
            //besitzt der Graph einen Eulerkreis?
            boolean eulerkreis = true;
            //Speicher Knoten mit ungeradem Grad
            Node[] odd = new Node[2];
            int i = 0;
            for (Node n : graph.nodes())
            {

                if (n.getNeighbours().keySet().size() % 2 == 1)
                {
                    eulerkreis = false;
                    odd[i] = n;
                    i++;
                }

            }


            int length = 0;
            //Jede Strasse wird genau einmal passiert
            for (String s : strassen)
            {
                length += s.length();
            }
            if (!eulerkreis)
            {
                //TODO: kürzesten Weg von einem ungeraden Knoten zum Anderen finden -> Floyd-Warshall
                //Summe der Grade aller Knoten positiv!!!! -> nicht 1 ungerader Knoten
                Node start = odd[0];
                Node end = odd[1];

                Node nowAt = start;
                start.setPathLength(0);
                PriorityQueue<Node> open = new PriorityQueue<Node>();
                open.offer(start);
                while (!open.isEmpty())
                {
                    nowAt = open.poll();
                    for (Node n : nowAt.getNeighbours().keySet())
                    {
                        int newPath = nowAt.pathLength + nowAt.getNeighbours().get(n);
                        if (n.pathLength > newPath)
                        {
                            n.setPathLength(newPath);
                            open.offer(n);
                        }
                    }

                }
                //Wegkosten errechnen:
                length += graph.get(end).getPathLength();


//                graph.get(odd[i]);
            }
            System.out.println(length);

        }
        //nichts mehr zu lesen -> Ende Programm
        while (input.ready());
    }

    private static class Node implements Comparable<Node>
    {

        private final char name;
        private final Map<Node, Integer> neighbours;
        private int pathLength = Integer.MAX_VALUE;
        private Node pred = null;

        public Node getPred()
        {
            return pred;
        }

        public void setPred(Node pred)
        {
            this.pred = pred;
        }

        public int getPathLength()
        {
            return pathLength;
        }

        public void setPathLength(int pathLength)
        {
            this.pathLength = pathLength;
        }

        void add(char n, int costs)
        {

            if (graph.get(n) == null)
            {
                graph.add(new Node(n));
            }
            neighbours.put(graph.get(n), costs);
            graph.get(n).getNeighbours().put(this, costs);
        }

        Node(char name)
        {
            this.name = name;
            neighbours = new HashMap<Node, Integer>();
        }

        public char getName()
        {
            return name;
        }

        public Map<Node, Integer> getNeighbours()
        {
            return neighbours;
        }

        @Override
        public int hashCode()
        {
            return (int) name;
        }

        @Override
        public boolean equals(Object obj)
        {
            if (obj == null)
            {
                return false;
            }
            if (getClass() != obj.getClass())
            {
                return false;
            }
            final Node other = (Node) obj;
            if (this.name != other.name)
            {
                return false;
            }
            return true;
        }

        @Override
        public int compareTo(Node o)
        {
            return this.pathLength - o.getPathLength();
        }

        @Override
        public String toString()
        {
            return "Node[" + name + "]";
        }
    }

    private static class Graph
    {

        private final List<Node> nodes;

        Graph()
        {
            nodes = new LinkedList<Node>();
        }

        boolean contains(char name)
        {
            return nodes.contains(new Node(name));
        }

        List<Node> nodes()
        {
            return nodes;
        }

        Node get(char name)
        {
            for (Node n : nodes)
            {
                if (n.getName() == name)
                {
                    return n;
                }
            }
            return null;
        }

        Node get(Node m)
        {
            return get(m.getName());
        }

        void add(Node n)
        {
            nodes.add(n);
        }
    }
}