曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

6046: 最近公共祖先

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：31 Solved：19
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

对于有根树T的两个结点u、v，最近公共祖先LCA(u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。
规定自己也看做是自己的祖先。即若u是v的祖先，则u、v的最近公共祖先为u。
给你一棵n个节点的有根树，节点标号为1~n，1号节点为根节点。
现在询问节点u、v的最近公共祖先是哪个节点。

Input

第一行三个整数n，u，v。
以后n行，每行若干个整数。第i行，第一个数为mi，表示节点i的子节点个数。紧接着mi个整数，表示节点i子节点的编号。保证父节点编号小于子节点。
n≤50

Output

一行，一个整数，表示u、v的最近公共祖先。

Sample Input Copy 

3 2 3
2 2 3
0
0

Sample Output Copy 

1

Source/Category