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

标签: 传统 | 时间限制: 2000 ms | 内存限制: 4 MiB |

题目描述

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

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

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

输入

输出

1
2

$n \leq 900000, m \leq 100000$