【题目描述】

给出充足的父子关系，请你编写程序找到某个人的最早的祖先。

规定每个人的名字都没有空格，且没有任意两个人的名字相同。最多可能有1000组父子关系，总人数最多可能达到50000人，家谱中的记载不超过30代。

【输入描述】

输入由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系中父亲只有一行，儿子可能有若干行；用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子的名字，儿子的名字一定紧接着父亲的名字出现；

接下来用?name的形式表示要求该人的最早的祖先；（?name一定在父子关系描述结束之后出现）

最后用单独的一个$表示文件结束。

【输出描述】

按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式：本人的名字+一个空格+祖先的名字+回车。

【样例输入】

#George  +Rodney  #Arthur  +Gareth  +Walter  #Gareth  +Edward  ?Edward  ?Walter  ?Rodney  ?Arthur  $

【样例输出】

Edward Arthur  Walter Arthur  Rodney George  Arthur Arthur

【题目描述】

w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。

这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。

如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？

【输入描述】

第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。

接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)

接下来k行，第2+k行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。

格子的编号一行一行，从上到下，从左到右编号。

比如：5 * 4 的小格子，编号：

1 2 3 4  5 6 7 8  9 10 11 12  13 14 15 16  17 18 19 20

【输出描述】

一行，表示有多少株?

【样例输入】

5 4  16  2 3  1 5  5 9  4 8  7 8  9 10  10 11  11 12  10 14  12 16  14 18  17 18  15 19  19 20  9 13  13 17

【样例输出】

5

【题目描述】

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

【输入描述】

第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。

以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。

接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。

【输出描述】

P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系

【样例输入】

6 5 3  1 2  1 5  3 4  5 2  1 3  1 4  2 3  5 6

【样例输出】

Yes  Yes  No