已知一颗树的节点间关系，请编程实现该树的先根遍历。输入：若干行,每行描述了一组双亲节点和孩子节点的关系序偶对(每个节点用不同的大写字母表示,节点小于26个)。且树的度小于5。输出：该树的先根遍历序列，序列中每个字母用空格隔开。

可以使用递归的方式实现先根遍历。具体实现如下：

# 定义树节点类
class Node:
    def __init__(self, val):
        self.val = val
        self.children = []

# 递归实现先根遍历
def preorder_traversal(root):
    if not root:
        return []
    res = [root.val]
    for child in root.children:
        res += preorder_traversal(child)
    return res

# 构建树
def build_tree(relations):
    nodes = {}
    for relation in relations:
        parent, child = relation.split()
        if parent not in nodes:
            nodes[parent] = Node(parent)
        if child not in nodes:
            nodes[child] = Node(child)
        nodes[parent].children.append(nodes[child])
    return nodes[relations[0].split()[0]]

# 主函数
if __name__ == "__main__":
    relations = []
    while True:
        try:
            relation = input().strip()
            if not relation:
                break
            relations.append(relation)
        except:
            break
    root = build_tree(relations)
    res = preorder_traversal(root)
    print(" ".join(res))

输入样例：

A B
A C
B D
B E
C F
C G
D H
E I

输出样例：

A B D H E I C F G