#6115. 「2017 山东二轮集训 Day6」汇合

内存限制:4 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

n 个人,他们构成了一颗有根树,每个人只能往他的父亲走,现在有 m 个询问,每次询问 A 和 B 想要汇合的话,最近汇点是哪一个。

输入格式

第一行两个正整数 n
接下来 n - 1 行每行一个正整数,依次表示点 2 \sim n 的父亲,保证每个点的父亲小于它本身。
接下来 m 行每行两个数表示一个询问。

输出格式

对每个询问单独输出一行表示答案。

样例

样例输入

5 2
1
1
2
2
3 5
4 5

样例输出

1
2

数据范围与提示

n \leq 900000, m \leq 100000