消息查找

题目描述

⼩ A 的消息记录中有 条消息，依次以 编号。编号⼩的消息发送时间早于编号⼤的消息。 ⼀条消息可以引⽤⼀条编号⼩于它的消息，也可以不引⽤消息。⼩ A 注意到消息记录⾥有引⽤的消息数量不会⾮常 多。消息记录的⼀个例⼦是： 【消息 1】小 A：有人做了今天的第一题吗？ 【消息 2】小 A：我第一题 WA 了，可能是什么原因？ 【消息 3：引用消息 1】小 B：我我我 【消息 4：引用消息 2】小 C：我也 WA 了 【消息 5：引用消息 2】小 B：是不是没开 long long？ 【消息 6：引用消息 5】小 A：改了就 AC 了，太厉害了！ 对于消息 （ ），⼩ A 以 标记消息 是否有引⽤，以及所引⽤的消息编号。如果 ，则消息 为引 ⽤了消息 ；如果 ，则消息 没有引⽤消息。 消息记录⾥有⾮常多条消息。为了快速查找所需要的消息，⼩ A 准备实现⼀个简单的消息查找⼯具。消息查找⼯具 任意时刻只能定位恰好⼀条消息，如果当前位于消息 （ ），那么接下来可以选择以下两种操作之⼀： 定位到消息 ； 如果消息 引⽤了消息 ，定位到消息 。 以上操作可以执⾏任意次（包括零次）。 ⼩ A 有 次询问。在第 （ ）次询问中，⼩ A 给出消息编号 （ ）。⼩ A 想知道，如果当前消 息查找⼯具位于 ，⾄少需要多少次操作才能定位到消息 。

输入格式

第⼀⾏，两个正整数 ，分别表⽰消息条数与询问次数。 第⼆⾏， 个⾮负整数 ，表⽰消息的引⽤关系，具体含义见题⽬描述。 接下来 ⾏中的第 ⾏（ ）包含两个正整数 ，表⽰⼀次询问。 保证⾄多只有 条引⽤消息。

输出格式

输出 ⾏，每⾏⼀个整数，表⽰将界⾯从消息 切换到消息 所需的最少操作次数。

样例输入 #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

数据范围

对于 的测试点，保证 ， 。 对于所有测试点，保证 ， ， ， ，保证⾄多有 条引⽤消息。

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度等级：⭐⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。