#!/usr/bin/env python
import os
from pprint import (pformat, pprint)
import sys

realms = set()
trusts = {}
paths = {}

inf = float("inf")

def trace(*a):
    if os.environ.get("DEBUG"):
        print("#", *a)

def add_trust(src, dst, bidirectional=False):
    if src in trusts:
        if type(trusts[src]) != set:
            trusts[src] = set(trusts[src])
        trusts[src].add(dst)
    else:
        trusts[src] = {dst}

def count_tabs(s):
    n = 0
    while n < len(s) and s[n] == "\t":
        n += 1
    return n

def parse_trusts(fh):
    depth = 0
    path = [None]
    for line in fh:
        indent = count_tabs(line)
        realm = line.strip()
        flags = set()
        if not realm or realm.startswith("#"):
            continue

        if realm.startswith(">"):
            flags.add("out")
            realm = realm[1:]

        realms.add(realm)

        if indent > depth:
            if (indent - depth > 1) or (path[0] is None):
                print("parse error: excessive indent")
                return
            depth += 1
            path.append(realm)
            trace(depth, "  "*depth, "--> %r @ %r" % (realm, path))
        elif indent < depth:
            while indent < depth:
                path.pop()
                depth -= 1
            path[-1] = realm
            trace(depth, "  "*depth, "<-- %r @ %r" % (realm, path))
        else:
            path[-1] = realm
            trace(depth, "  "*depth, "... %r @ %r" % (realm, path))

        if depth > 0:
            a = path[-2]
            b = path[-1]
            yield (a, b)
            if "out" not in flags:
                yield (b, a)

def load_trusts(fh):
    for a, b in parse_trusts(fh):
        add_trust(a, b)

def dump_trusts():
    for src in sorted(trusts):
        print("%s -> %s" % (src, trusts[src]))

def is_terminal():
    return hasattr(sys.stdout, "isatty") and sys.stdout.isatty()

def show_tree(root, tree, indent=0, highlight=None, ctx=None):
    """
    Print dict `tree` {item: [children...]} starting at a given `root`
    as a textual tree. Recurse for each item in `tree[root]` as new root.

    >>> tree = {"a": {"b", "c"}, "b": {"d"}, "c": {"b", "d"}}
    >>> show_tree("a", tree)
    a
    ├─b
    │ └─d
    └─c
      ├─b
      │ └─d
      └─d
    """
    depth, branches, seen = ctx or (0, [], set())
    if depth == 0:
        print(" "*indent + root)
    if root not in tree:
        return
    branches += [None]
    seen |= {root}
    if not highlight:
        highlight = dict()
    children = set(tree[root]) - seen
    more = len(children)
    for child in sorted(children):
        more -= 1
        branches[depth] = ("├" if more else "└") + "─"
        prefix = suffix = ""
        if is_terminal() and child in highlight:
            color = highlight[child]
            prefix = "\033[%sm" % color
            suffix = "\033[m"
        print(" "*indent + "".join(branches) + prefix + child + suffix)
        if child in tree:
            branches[depth] = ("│" if more else " ") + " "
            ctx = depth + 1, branches.copy(), seen.copy()
            show_tree(child, tree, indent, highlight, ctx)

def find_path(src, dst, seen=None):
    if src == dst:
        return [src]

    if src not in trusts:
        return []

    if dst in trusts[src]:
        return [src, dst]

    best_dist = inf
    best_path = []
    seen = seen or {src}
    for via in trusts[src]:
        if via in seen:
            continue
        path = find_path(via, dst, seen | {via})
        dist = len(path) or inf
        if dist < best_dist:
            best_dist = dist
            best_path = [src] + path
    return best_path

def find_paths(src, dst, seen=None):
    if src == dst:
        yield [src]
    elif src not in trusts:
        yield []
    else:
        if dst in trusts[src]:
            yield [src, dst]
        seen = seen or {src}
        for via in sorted(trusts[src]):
            if via in seen:
                continue
            for i in find_paths(via, dst, seen | {via}):
                yield [src] + i

def create_paths():
    realms = list(trusts)
    realms.sort()
    for src in realms:
        for dst in realms:
            if (dst, src) in paths:
                paths[src, dst] = paths[dst, src][::-1]
            else:
                paths[src, dst] = find_path(src, dst)

def dump_paths():
    for pair in sorted(paths):
        src, dst = pair
        if paths[pair]:
            print(repr(pair))
            output = pformat(paths[pair], width=72, compact=True)
            for line in output.split("\n"):
                print("\t%s" % line)
            print()

def dump_capaths():
    print("[capaths]")
    realms = list(trusts)
    realms.sort()
    for src in sorted(realms):
        print("\t%s = {" % src)
        for dst in realms:
            if src == dst:
                continue
            path = paths[src, dst]
            #print("\t\t\033[38;5;239m# %s via {%s}\033[m" % (dst, ", ".join(path)))
            if len(path) < 2:
                # 0 hops means "no path"
                # 1 hop means the only hop is ourselves, which is filtered out above
                print("\t\t# no path to %s" % dst)
                continue
            # 2 or more hops means src is the first hop, dst is last
            # discard both, and ensure there's still at least one subtag
            path = path[1:-1] or ["."]
            for hop in path:
                print("\t\t%s = %s" % (dst, hop))
        print("\t}")
    print()

if __name__ == "__main__":
    try:
        cmd = sys.argv.pop(1)
    except IndexError:
        cmd = "capaths"

    load_trusts(sys.stdin)

    create_paths()

    if cmd == "all":
        def printh(s):
            print()
            print("= %s =" % s)
            print()
        printh("Trusts")
        dump_trusts()
        printh("Paths")
        dump_paths()
        printh("Capaths")
        dump_capaths()
    elif cmd == "trusts":
        dump_trusts()
    elif cmd == "paths":
        dump_paths()
    elif cmd == "capaths":
        dump_capaths()
    elif cmd == "find-path":
        src, dst = sys.argv[1:]
        path = find_path(src, dst)
        print(*path)
    elif cmd == "find-paths":
        src, dst = sys.argv[1:]
        for path in find_paths(src, dst):
            print(*path)
    elif cmd == "peers":
        src = sys.argv[1]
        peers = trusts.get(src, set())
        for dst in sorted(peers):
            print(dst)
    elif cmd == "tree":
        srcs = sys.argv[1:] or sorted(realms)
        for src in srcs:
            show_tree(src, trusts)
