import java.io.*;
import java.net.*;
import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public class Graph<T> {
    public final Map<T, Collection<T>> adjacencies;
    public final Supplier<? extends Collection<T>> collectionSupplier;

    public Graph() {
        this(new LinkedHashMap<>(), ArrayList<T>::new);
    }

    public Graph(Map<T, Collection<T>> adjacencies,
            Supplier<? extends Collection<T>> collectionSupplier) {
        this.adjacencies = adjacencies;
        this.collectionSupplier = collectionSupplier;
    }

    public static String urlEncode(String str) {
        try {
            return URLEncoder.encode(str, "UTF-8");
        } catch (UnsupportedEncodingException e) {
            throw new RuntimeException("No UTF-8 support.", e);
        }
    }

    public static String urlDecode(String str) {
        try {
            return URLDecoder.decode(str, "UTF-8");
        } catch (UnsupportedEncodingException e) {
            throw new RuntimeException("No UTF-8 support.", e);
        }
    }

    public void fromString(String str, Function<String, T> parseTag) {
        int end = str.indexOf('{');
        int arrow;
        while ((arrow = str.indexOf("->", end + 1)) != -1) {
            T tag = parseTag.apply(urlDecode(
                str.substring(end + 1, arrow).trim()));
            int start = str.indexOf('{', arrow + 2) + 1;
            if (start == 0) {
                break;
            }
            end = str.indexOf('}', start);
            if (end == -1) {
                break;
            }
            Collection<T> collection;
            if (adjacencies.containsKey(tag)) {
                collection = adjacencies.get(tag);
            } else {
                collection = collectionSupplier.get();
                adjacencies.put(tag, collection);
            }
            Arrays.stream(str.substring(start, end).trim().split("\\s+"))
                .map(s -> s.trim())
                .filter(s -> !s.isEmpty())
                .map(s -> parseTag.apply(urlDecode(s)))
                .forEachOrdered(t -> {
                    collection.add(t);
                    if (!adjacencies.containsKey(t)) {
                        adjacencies.put(t, collectionSupplier.get());
                    }
                });
        }
    }

    public void fromBreadthFirstSearchTree(Graph<T> graph, T start) {
        Queue<T> queue = new ArrayDeque<>();
        adjacencies.put(start, collectionSupplier.get());
        queue.add(start);
        while (queue.peek() != null) {
            T tag = queue.remove();
            for (T adjacent : graph.adjacencies.get(tag)) {
                if (!adjacencies.containsKey(adjacent)) {
                    adjacencies.put(adjacent, collectionSupplier.get());
                    adjacencies.get(tag).add(adjacent);
                    queue.add(adjacent);
                }
            }
        }
    }

    @Override
    public String toString() {
        return "Graph {"
            + adjacencies.entrySet().parallelStream()
                .map(entry -> String.format("\n  %s -> { %s }",
                    urlEncode(entry.getKey().toString()),
                    entry.getValue().parallelStream()
                        .map(n -> urlEncode(n.toString()))
                        .collect(Collectors.joining(" "))))
                .reduce("", String::concat)
            + "\n}";
    }

    public static void main(String[] args) {
        try {
            String input = new String(System.in.readAllBytes());
            int startEnd = input.indexOf('{');
            String start = urlDecode(input.substring(0, startEnd).trim());
            Graph<String> graph = new Graph<>();
            graph.fromString(input, s -> s);
            System.out.println("Input graph: " + graph);
            System.out.println("Starting node: " + urlEncode(start));
            Graph<String> tree = new Graph<>();
            tree.fromBreadthFirstSearchTree(graph, start);
            System.out.println("Breadth-first order: {");
            for (String tag : tree.adjacencies.keySet()) {
                System.out.println("  " + urlEncode(tag));
            }
            System.out.println("}");
            System.out.println("Breadth-first tree: " + tree);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

$ cat test.graph
Frank {
  Frank -> {Mann Wurz Kassel}
  Mann -> {Frank Karls}
  Karls -> {Mann Augs}
  Augs -> {Karls Mun}
  Mun -> {Augs Nurn Kassel}
  Nurn -> {Wurz Stutt}
  Wurz -> {Frank Erf Nurn}
  Erf -> {Wurz}
  Stutt -> {Nurn}
  Kassel -> {Frank Mun}
}
$ java Graph < test.graph
Input graph: Graph {
  Frank -> { Mann Wurz Kassel }
  Mann -> { Frank Karls }
  Karls -> { Mann Augs }
  Augs -> { Karls Mun }
  Mun -> { Augs Nurn Kassel }
  Nurn -> { Wurz Stutt }
  Wurz -> { Frank Erf Nurn }
  Erf -> { Wurz }
  Stutt -> { Nurn }
  Kassel -> { Frank Mun }
}
Starting node: Frank
Breadth-first order: {
  Frank
  Mann
  Wurz
  Kassel
  Karls
  Erf
  Nurn
  Mun
  Augs
  Stutt
}
Breadth-first tree: Graph {
  Frank -> { Mann Wurz Kassel }
  Mann -> { Karls }
  Wurz -> { Erf Nurn }
  Kassel -> { Mun }
  Karls -> { Augs }
  Erf -> {  }
  Nurn -> { Stutt }
  Mun -> {  }
  Augs -> {  }
  Stutt -> {  }
}
$ cat tree.graph
a {
  a -> {b c}
  b -> {d e}
  e -> {h}
  c -> {f g}
}
$ java Graph < tree.graph
Input graph: Graph {
  a -> { b c }
  b -> { d e }
  c -> { f g }
  d -> {  }
  e -> { h }
  h -> {  }
  f -> {  }
  g -> {  }
}
Starting node: a
Breadth-first order: {
  a
  b
  c
  d
  e
  f
  g
  h
}
Breadth-first tree: Graph {
  a -> { b c }
  b -> { d e }
  c -> { f g }
  d -> {  }
  e -> { h }
  f -> {  }
  g -> {  }
  h -> {  }
}