#!/usr/bin/python
# coding: utf-8

class Node:
    def __init__(self, parent, children):
        self.parent = parent
        self.children = children

    def output(self, depth=0): # составляем строку (поиском в глубину), чтобы её можно было вывести на экран
        res = ' '*depth + str(self)
        for ch in self.children:
            res += '\n' + ch.output(depth+4) # 4 - кол-во пробелов, которыми делается отступ
        return res

    def append_child(self):
        node = Node(self, [])
        self.children.append(node)
        return node

    def path_to_root(self):
        if self.parent:
            return [self,] + self.parent.path_to_root()
        else:
            return [self]

    def path_to_node(self, node):
        pth1 = self.path_to_root()
        pth2 = node.path_to_root()
        pth1.reverse()
        pth2.reverse()

        if pth1[0] != pth2[0]:
            return None

        pth1 += [1,]
        pth2 += [2,]
        lca = 0
        while pth1[lca] == pth2[lca]:
            lca += 1

        pth1.reverse()
        res = pth1[1:len(pth1)-lca+1] + pth2[lca:-1]

        return res

    def leaves(self):
        res = []
        for ch in self.children:
            if ch.children:
                res += ch.leaves()
            else:
                res.append(ch)
        return res

class Tree:
    def __init__(self, root): # root - объект типа Node
        self.root = root

    def output(self):
        return self.root.output()

class GenNode(Node):
    def __init__(self, parent, name):
        Node.__init__(self, parent, [])
        self.name = name

    def __str__(self):
        return self.name

    def append_child(self, name):
        node = GenNode(self, name)
        self.children.append(node)
        return node

    def get_brothers(self):
        res = []
        if self.parent:
            res = self.parent.children
        return res

    def get_uncles(self):
        res = []
        grandfather = self.get_grandfather()
        if grandfather:
            res = [x for x in grandfather.children if x != self.parent]
        return res

    def get_grandfather(self):
        res = None
        if self.parent:
            if self.parent.parent:
                res = self.parent.parent
        return res

    def get_grandchildren(self):
        res = []
        for ch in self.children:
            for gch in ch.children:
                res.append(gch)
        return res

class GenTree(Tree):
    pass

# Итак, демонстрация

rickard = GenNode(None, 'Rickard Stark')

eddard = rickard.append_child('Eddard Stark')
brandon = rickard.append_child('Brandon Stark')
benjen = rickard.append_child('Benjen Stark')

robb = eddard.append_child('Robb Stark')
bran = eddard.append_child('Bran Stark')
rickon = eddard.append_child('Rickon Stark')
jon = eddard.append_child('Jon Snow')

tree = Tree(rickard)

print 'Выведем всё древо:'
print
print tree.output()
print

print 'Выведем братьев Эддарда:'
for x in eddard.get_brothers():
    print x
print

print 'Выведем внуков Рикарда:'
for x in rickard.get_grandchildren():
    print x
print

print 'Выведем дедушку Джона Сноу:'
print jon.get_grandfather()
print

print 'Выведем дядь Джона Сноу:'
for x in jon.get_uncles():
    print x
print

print 'Выведем jon.path_to_root():'
print [str(x) for x in jon.path_to_root()]
print

print 'Выведем rickard.leaves():'
print [str(x) for x in rickard.leaves()]
print

print 'Выведем jon.path_to_node(benjen):'
print [str(x) for x in jon.path_to_node(benjen)]