# 柯里昂家族树

在《教父》中，柯里昂家族是一个著名的黑手党家族，由家族的首领柯里昂（Don Corleone）和他的四个儿子构成。柯里昂家族的家谱是一棵二叉树，其中柯里昂是根节点，他的儿子们分别是他的左儿子和右儿子。

现在，你需要编写一个程序，读入一个包含若干行的字符串，每行表示一个人的信息。每行的格式如下：

<人物名称> is the <父亲名称>'s <儿子>

其中，人物名称是一个不包含空格的字符串，父亲名称和儿子也是一个不包含空格的字符串。

例如，下面是一棵柯里昂家族的家谱：

Don Corleone is the Don's son
Fredo Corleone is the Don's son
Michael Corleone is the Don's son
Tom Hagen is the Don's adopted son

你的程序需要按照这些信息建立一棵二叉树，并输出这棵树的前序遍历。

例如，对于上面的家谱，输出应该是：

Don Corleone Fredo Corleone Michael Corleone Tom Hagen

你的程序需要支持以下功能：

 - 建立二叉树。你需要定义一个结构体表示一个节点，包含人物名称、左儿子和右儿子三个字段。你需要编写一个函数，读入若干行字符串，根据字符串中的信息建立二叉树。

 - 输出前序遍历。你需要编写一个函数，输出给定二叉树的前序遍历。
## 输入格式
输入的第一行包含一个整数 n（1 <= n <= 1000），表示字符串的行数。

接下来的 n 行，每行包含一个字符串，表示一个人的信息。字符串的格式如上文所述。

## 输出格式
输出给定二叉树的前序遍历，每个人物名称占一行。

## 输入样例

4
Don Corleone is the Don's son
Fredo Corleone is the Don's son
Michael Corleone is the Don's son
Tom Hagen is the Don's adopted son

## 输出样例

Don Corleone
Fredo Corleone
Michael Corleone
Tom Hagen

## 提示

1. 人物名称和父亲名称均由不超过 100 个字符组成，且不包含空格；

2. 儿子的值可能是 "son" 或 "adopted son"；

3. 输入中可能会出现重名的人物，你的程序需要处理这种情况；

4. 输入的字符串保证是合法的，不会出现父亲名称找不到的情况。