A67851 | 消息查找

试题名称：消息查找 

时间限制：1.0 s 

内存限制：512.0 MB 

3.1.1 题目描述 

小 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 以r_i标记消息i是否有引用，以及所引用的消息编号。如果r_i＞0 ，则消息i为引用了消息r_i；如果r_i=0，则消息i没有引用消息。 

消息记录里有非常多条消息。为了快速查找所需要的消息，小 A 准备实现一个简单的消息查找工具。消息查找工具任意时刻只能定位恰好一条消息，如果当前位于消息i（1＜i＜n ），那么接下来可以选择以下两种操作之一： 

定位到消息i-1； 

如果消息i引用了消息r_i，定位到消息r_i。 

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

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

3.1.2 输入格式 

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

第二行，n个非负整数r₁,r₂,…,r_n，表示消息的引用关系，具体含义见题目描述。 

接下来q行中的第k行（1≤k≤q）包含两个正整数x_k,y_k，表示一次询问。 

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

3.1.3 输出格式 

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

3.1.4 样例 

3.1.4.1 输入样例 

1 3.1.4.2 输出样例 1 

3.1.4.3 输入样例 2 

3.1.4.4 输出样例 2 

3.1.5 数据范围 

对于40%的测试点，保证1≤n≤2000，1≤q≤2000。 

对于所有测试点，保证1≤n≤10⁵，1≤q≤10⁵，o≤r_i＜i，1≤y_k≤x_k≤n，保证至多有1000条引用消息。