消息查找：求从x到y的最少操作次数

题目描述

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

一条消息可以引用一条编号小于它的消息，也可以不引用消息。小A注意到消息记录里有引用的消息数量不会非常多。

对于消息i（1≤i≤n），小A以r_i标记消息i是否有引用，以及所引用的消息编号。如果r_i＞0，则消息i引用了消息r_i；如果r_i=0，则消息i没有引用消息。

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

1. 定位到消息i-1；
2. 如果消息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。

输入格式

第一行，两个正整数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条引用消息。