给你一棵有根树，求出这棵树上若干对节点的最近公共祖先。两个节点共同拥有的祖先叫做它们的公共祖先，它们公共祖先中离它们最近的一个叫做它们的最近公共祖先。
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