6111 - GESP:2026-3月等级8-T1-消息查找
小 A 的消息记录中有 n条消息，依次以1,2...n 编号。编号小的消息发送时间早于编号大的消息。 一条消息可以引用一条编号小于它的消息，也可以不引用消息。小 A 注意到消息记录里有引用的消息数量不会非常多。消息记录的一个例子是：
【消息 1】小 A：有人做了今天的第一题吗？
【消息 2】小 A：我第一题 WA 了，可能是什么原因？
【消息 3：引用消息 1】小 B：我我我
【消息 4：引用消息 2】小 C：我也 WA 了
【消息 5：引用消息 2】小 B：是不是没开 long long ？
【消息 6：引用消息 5】小 A：改了就 AC 了，太厉害了！
对于消息 i（1<=i<=n ），小 A 以ri 标记消息 i是否有引用，以及所引用的消息编号。如果ri>0 ，则消息i 为引用了消息ri ；如果ri=0 ，则消息i 没有引用消息。 消息记录里有非常多条消息。为了快速查找所需要的消息，小 A 准备实现一个简单的消息查找工具。消息查找工具任意时刻只能定位恰好一条消息，如果当前位于消息i （1 < i <= n ），那么接下来可以选择以下两种操作之一： 1.定位到消息 i-1； 2.如果消息i 引用了消息ri ，定位到消息ri 。 以上操作可以执行任意次（包括零次）。 小 A 有q 次询问。在第k （ 1<=k<=q）次询问中，小 A 给出消息编号 xk,yk（yk < xk ）。小 A 想知道，如果当前消息查找工具位于 xk，至少需要多少次操作才能定位到消息yk 。
Input
第一行，两个正整数 n,q，分别表示消息条数与询问次数。 第二行，n 个非负整数r1,r2...rn ，表示消息的引用关系，具体含义见题目描述。 接下来q 行中的第k 行（1<=k<=q ）包含两个正整数xk,yk ，表示一次询问。 保证至多只有 1000条引用消息
Output
输出q 行，每行一个整数，表示将界面从消息xk 切换到消息yk 所需的最少操作次数
Examples
Input
6 3 0 0 1 2 2 5 4 1 6 2 6 3
Output
2 2 3
Input
5 5 0 0 0 1 3 4 1 4 2 5 1 5 2 5 3
Output
1 2 2 2 1
Hint
数据范围 对于40% 的测试点，保证1<=n<=2000 ，1<=q<=2000 。 对于所有测试点，保证1<=n<=10^5 ，1<=q<=10^5 ，0<=ri < i,1<=yk< xk<=n ，保证至多有1000 条引用消息