时间限制：1秒　　内存限制：256M

---

【问题描述】

　　给出一棵有根树，和若干询问：\(u,v\)，表示询问结点 \(u,v\) 的最近公共祖先。例如，考虑下面这棵树：

　　以下是6个询问的最近公共祖先：

【输入格式】

　　第一行: 用空格隔开的两个数字: \(N\) 和 \(M\)，表示树的结点数量为N，有M个询问：
　　第 2..\(N\) 行: 第 \(i\) 行 \(P_i\)
　　第 \(N+1..N+M\) 行: 第 \(k+N\) 行：\(u\) 和 \(v\)。

【输出格式】

　　第 \(1..M\) 行:第 \(j\) 个询问的最近公共祖先。

【输入输出样例】

　Input

9 6
1
1
2
8
1
8
6
6
2 7
4 2
3 3
4 1
7 5
9 5

　Output

1
2
3
1
8
6

【数据说明】

　　对于 \(100\%\) 的数据 \(1≤N≤1000\)，\(1≤M≤1,000\)。

【来源】

　　Mr.he