from json import dumps


class Tree(object):
    def __init__(self, label, children=[]):
        self.label = label
        self.children = children

    def __dict__(self):
        return {self.label: [c.__dict__() for c in sorted(self.children)]}

    def __str__(self, indent=None):
        return dumps(self.__dict__(), indent=indent)

    def __lt__(self, other):
        return self.label < other.label

    def __eq__(self, other):
        return self.__dict__() == other.__dict__()

    def __iter__(self):
        yield self.label
        for child in self.children:
            for gchild in child:
                yield gchild

    def dup(self):
        return Tree(self.label, [c.dup() for c in self.children])

    def add(self, other):
        tree = self.dup()
        tree.children.append(other)
        return tree

    def remove(self, node):
        tree = self.dup()
        for child in list(tree.children):
            tree.children.remove(child)
            if child.label == node:
                break
            tree.children.append(child.remove(node))
        return tree

    def fromPov(self, from_node):
        stack = [self]
        visited = set()
        while stack:
            tree = stack.pop(0)
            if tree.label in visited:
                continue
            visited.add(tree.label)
            if from_node == tree.label:
                return tree
            for child in tree.children:
                stack.append(child.add(tree.remove(child.label)))
        raise ValueError()

    def pathTo(self, from_node, to_node):
        reordered = self.fromPov(from_node)
        stack = reordered.children
        path = [from_node]
        while path[-1] != to_node:
            try:
                tree = stack.pop()
            except IndexError:
                raise ValueError()
            if to_node in tree:
                path.append(tree.label)
                stack = tree.children
        return path