练习专区

除夕祭祖，是中国流传至今的传统风俗之一。一方面是源于“百善孝为先”和“慎终追远”的传统观念，在辞旧迎新之际对祖宗先辈表示孝敬之意和表达怀念之情；另一方面是由于人们深信祖先神灵可以保佑子孙后代，使子孙后代兴旺发达。这一传统习俗代代相传，人们每逢除夕总要举行祭祀仪式，感恩追始，祈求保佑。在过去，祭祖仪式一般在除夕下午在族人祠堂举行，身穿盛装的同一姓氏宗族参加，仪式较为隆重。有些地方祭祖活动中的一项重要内容就是登记家谱，将家里新添的人丁记录在家谱上。 现在有些地方对家谱也实现了电子化，现在要求你编写程序将某个家族新添的人丁加入到家谱中去，并输出。由于现在实行了计划生育，一对夫妇最多生育2个孩子，所以最新的家谱采用二叉树的方式来存储信息。

第1行是个正整数N，表示这个家族的完全二叉树形式的结点个数。当N为0时结束程序。 第2行是中间用空格分隔的N个字符，表示现有的家族所有成员的信息。输入按照完全二叉树的顺序存储格式输入，没有的结点以#代替。 第3行是一个正整数M，表示有M个新添人口的信息需要输入。 接下来的M行数据，每行有两个人名，第一个是父亲的名字，第二个是要新添的孩子的名字。如果该孩子是该父亲的第一个孩子则插入在该父亲的左边，若是其第二个孩子则插入在其右边。

输出新添的孩子是家族的第几代，并输出他以及他的所有祖先的名字。

7
A B C D # E #
2
B F
E G
1
A
2
A B
A C
0

B的孩子F是家族的第3代.家族传承的顺序是A-B-F.
E的孩子G是家族的第4代.家族传承的顺序是A-C-E-G.
A的孩子B是家族的第2代.家族传承的顺序是A-B.
A的孩子C是?易宓牡?2代.家族传承的顺序是A-C.