from io import StringIO

# Creating an iterator out of a class that implements __getitem__, but not
# __iter__.  This is a reconstruction of how the built-in iter function might
# do it.

class GetitemIterator:
    
    def __init__(self, anIterable):
        """An iterator over ANITERABLE, which must implement __getitem__.
           This iterator returns ANITERABLE[0], ANITERABLE[1], ... up
           to and not including the first index that causes an
           IndexError or StopIteration."""
        self._iterable = anIterable
        self._nextIndex = 0

    def __next__(self):
        try:
            v = self._iterable[self._nextIndex]
            self._nextIndex += 1
            return v
        except IndexError:
            raise StopIteration


# A reconstruction of the standard range class (fancy version, allowing
# backwards ranges.)

class Range:
    def __init__(self, first, end, step=1):
        assert step != 0
        self._first, self._end, self._step = first, end, step
        if step > 0:
            self._len = max(0, self._end - self._first + self._step - 1) // self._step
        else:
            self._len = max(0, self._first - self._end - self._step - 1) // -self._step

    def __len__(self):
        return self._len

    def __getitem__(self, k):
        if k < 0:
            k += self._len
        if 0 <= k < self._len:
            return self._first + k * self._step
        else:
            raise IndexError

    def __repr__(self):
        if self._step == 1:
            return "Range({}, {})".format(self._first, self._last)
        else:
            return "Range({}, {}, {})".format(self._first, self._last, self._step)

    def __iter__(self):
        return GetitemIterator(self)

class Link:
    empty = ()

    def __init__(self, first, rest=empty):
        self._first = first
        self._rest = rest

    def __getitem__(self, i):
        if i == 0:
            return self._first
        else:
            return self._rest[i-1]

    def __len__(self):
        return 1 + len(self._rest)

    # If __iter__ is omitted, Python can still work with __getitem__.!
    def __iter__(self):
        p = self
        while p is not Link.empty:
            yield p._first
            p = p._next

    def __str__(self):
        r = StringIO()
        print("(", file=r, end="")
        sep = ""
        for p in self:
            print(sep + repr(p), file=r, end="")
            sep = ", "
        print(")", file=r, end="")
        return r.getvalue()

    def __repr__(self):
        return "Link({}, {})".format(repr(self._first), repr(self._rest))

# Iterating over trees.

def preorderLabels(T):
    """Generate the labels of tree T in preorder (i.e., first the node 
    label, then the preorder labels of the branches.)"""
    yield label(T)
    for child in branches(T):
        yield from preorderLabels(child)