题目描述
小 A 的消息记录中有 $n$ 条消息，依次以 $1, 2, \ldots, n$ 编号。编号小的消息发送时间早于编号大的消息。
一条消息可以引用一条编号小于它的消息，也可以不引用消息。小 A 注意到消息记录里有引用的消息数量不会非常多。消息记录的一个例子是：
long long？对于消息 $i$（$1 \le i \le n$），小 A 以 $r_i$ 标记消息 $i$ 是否引用，以及所引用的消息编号。如果 $r_i > 0$，则消息 $i$ 引用了消息 $r_i$；如果 $r_i = 0$，则消息 $i$ 没有引用消息。
消息记录里有非常多消息。为了快速查找所需要的消息，小 A 准备实现一个简单的消息查找工具。消息查找工具任意时刻只能定位恰好一条消息。如果当前位于消息 $i$（$1 < i \le n$），那么接下来可以选择以下两种操作之一：
以上操作可以执行任意次（包括零次）。
小 A 有 $q$ 次询问。在第 $k$（$1 \le k \le q$）次询问中，小 A 给出消息编号 $x_k, y_k$（$y_k < x_k$）。小 A 想知道，如果当前消息查找工具位于 $x_k$，至少需要多少次操作才能定位到消息 $y_k$。
输入格式
第一行，两个正整数 $n, q$，分别表示消息条数与询问次数。
第二行，$n$ 个非负整数 $r_1, r_2, \ldots, r_n$，表示消息的引用关系，具体含义见题目描述。
接下来 $q$ 行中的第 $k$ 行（$1 \le k \le q$）包含两个正整数 $x_k, y_k$，表示一次询问。
保证至多有 1000 条引用消息。
输出格式
输出 $q$ 行，每行一个整数，表示将界面从消息 $x_k$ 切换到消息 $y_k$ 所需的最少操作次数。
输入样例 1
6 3
0 0 1 2 2 5
4 1
6 2
6 3输出样例 1
2
2
3输入样例 2
5 5
0 0 0 1 3
4 1
4 2
5 1
5 2
5 3输出样例 2
1
2
2
2
1数据范围
对于 40% 的测试点，保证 $1 \le n \le 2000$，$1 \le q \le 2000$。
对于所有测试点，保证 $1 \le n \le 10^5$，$1 \le q \le 10^5$，$0 \le r_i < i$，$1 \le y_k < x_k \le n$。保证至多有 1000 条引用消息。