给你一棵有根树,求出这棵树上若干对节点的最近公共祖先。两个节点共同拥有的祖先叫做它们的公共祖先,它们公共祖先中离它们最近的一个叫做它们的最近公共祖先。
Input
输入只包含正整数。
第一行两个数n,m(均不超过100000),表示树的节点个数和询问个数。树的节点从1到n编号。
接下来n行,描述这n个点的儿子节点。每行第一个数k,表示这个点儿子的个数。接下来k个数,分别为这个点的儿子。
接下来m行,描述m个询问。每行两个数a,b,表示询问a和b的最近公共祖先。
输入保证是一棵以1为根的树。所有表示节点的数均不超过[1,n]。
Output
m行,为输入中对应询问的答案。
Sample Input
10 10 4 3 2 4 5 0 0 1 8 1 6 0 0 3 10 9 7 0 0 7 7 7 6 4 8 10 8 1 3 2 3 3 4 6 1 9 1 5 3 Sample Output 7 1 4 8 1 1 1 1 1 1