消息查找

题目描述

小 A 的消息记录中有 n 条消息，依次以 1..n 编号。编号小的消息发送时间早于编号大的消息。 一条消息可以引用一条编号小于它的消息，也可以不引用消息。对于消息 i，用 ref[i] 标记：如果 ref[i] > 0，则消息 i 引用了消息 ref[i]；如果 ref[i] = 0，则消息 i 没有引用消息。 消息查找工具任意时刻只能定位恰好一条消息，如果当前位于消息 x，那么接下来可以选择以下两种操作之一：

• 定位到消息 x-1（若 x>1）；
• 如果消息 x 引用了消息 ref[x]，定位到消息 ref[x]。 以上操作可以执行任意次（包括零次）。 小 A 有 q 次询问，每次给出消息编号 x 和 y，求从消息 x 切换到消息 y 所需的最少操作次数。

输入格式

第一行，两个正整数 n, q，分别表示消息条数与询问次数。 第二行，n 个非负整数 ref[1..n]，表示消息的引用关系。 接下来 q 行中的第 i 行包含两个正整数 x, y，表示一次询问。

输出格式

输出 q 行，每行一个整数，表示将界面从消息 x 切换到消息 y 所需的最少操作次数。

样例

输入

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

输出

2
2
3

数据范围

保证 1 ≤ n ≤ 100000，1 ≤ q ≤ 100000，1 ≤ x, y ≤ n，0 ≤ ref[i] < i，保证引用关系稀疏（至多有 1000 条消息存在引用的消息或引用别的消息）。