题目描述

给定一棵$n$个节点的树，其中$1$号节点为根节点，以及$m$次询问，每次询问给出两个节点$u,v$，你需要回答他们的最近公共祖先是哪个节点。

输入格式

第一行输入两个整数$n,m$。 第二行输入$n$个整数$p_i(p_i<i)$，其中$p_i$表示节点$i$的父节点编号，保证只有$p_1=0$，表示节点$1$为根节点。 接下来$m$行，每行输入两个整数$u,v$，表示一次询问。

输出格式

输出共$m$行，每行输出一个整数，表示询问的答案。

样例输入 #1

7 5
0 1 1 3 3 5 3
2 3
4 5
5 7
6 7
2 7

样例输出 #1

1
3
3
3
1

说明/提示

有$1\leq n,m\leq 10^5,1\leq u,v\leq n$。