[GESP202603 八级] 消息查找

小 A 的消息记录中有 n 条消息，依次以 1, 2, ..., n 编号。编号小的消息发送时间早于编号大的消息。

一条消息可以引用一条编号小于它的消息，也可以不引用消息。对于消息 i（1 <= i <= n），小 A 以 r[i] 标记消息 i 是否有引用，以及所引用的消息编号。如果 r[i] > 0，则消息 i 引用了消息 r[i]；如果 r[i] = 0，则消息 i 没有引用消息。

消息查找工具任意时刻只能定位恰好一条消息，如果当前位于消息 i（1 < i <= n），那么接下来可以选择以下两种操作之一：

1. 定位到消息 i - 1；
2. 如果消息 i 引用了消息 r[i]，定位到消息 r[i]。

以上操作可以执行任意次（包括零次）。

小 A 有 q 次询问。在第 k 次询问中，小 A 给出消息编号 x[k], y[k]（y[k] < x[k]）。小 A 想知道，如果当前消息查找工具位于 x[k]，至少需要多少次操作才能定位到消息 y[k]。

第一行，两个正整数 n, q，分别表示消息条数与询问次数。

第二行，n 个非负整数 r[1], r[2], ..., r[n]，表示消息的引用关系。

接下来 q 行中的第 k 行（1 <= k <= q）包含两个正整数 x[k], y[k]，表示一次询问。

保证至多只有 1000 条引用消息。

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

• 对于 40% 的测试点，保证 1 <= n <= 2000，1 <= q <= 2000
• 对于所有测试点，保证 1 <= n <= 10^5，1 <= q <= 10^5，0 <= r[i] < i，1 <= y[k] < x[k] <= n
• 保证至多有 1000 条引用消息