2974: 最近祖先
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 0 Solved: 0
[Status] [Submit] [Creator:]
Description
小科知道小丁和自己有亲缘关系，但是他不知道他们具体的亲缘关系，于是他打开家谱想要找到答案，但是家谱太庞大了，没看一会小科已经头昏眼花了，你可以帮助小科找到他和小丁的最近的公共祖先吗？为简化计算可以将小科的家谱看作是一个树形结构，树中的每个结点都有一个编号（1-n)。
Input
第1行：n, m, k, d，n表示家谱树中结点的数量，m表示树中关系的数量，k表示小科的编号，d表示小丁的编号。
第2到m+1行：每行两个空格分隔的整数x, y，表示x是y的双亲。
第2到m+1行：每行两个空格分隔的整数x, y，表示x是y的双亲。
Output
一行：小科和小丁的最近公共祖先的编号。
Sample Input Copy
8 7 6 8
1 2
1 3
2 4
2 5
4 6
5 7
5 8
Sample Output Copy
2
HINT
数据范围：n, m, k, d <= 100;
样例说明：
样例中的家谱树如下图：
小科的编号为6， 小丁的编号为8， 编号为2的结点是他们最近的公共祖先。
样例说明：
样例中的家谱树如下图：
小科的编号为6， 小丁的编号为8， 编号为2的结点是他们最近的公共祖先。