Background

Related multiple-choice and true/false problems: https://ti.luogu.com.cn/problemset/1212.

Problem Description

There are $n$ messages in A's chat history, numbered $1, 2, \dots, n$ in order. A message with a smaller number was sent earlier than a message with a larger number.

A message may quote a message with a smaller number, or it may quote nothing. A noticed that the number of messages that contain quotes will not be very large. An example of a chat history is:

• [Message 1] A: Has anyone done today's first problem?
• [Message 2] A: I got WA on the first problem, what could be the reason?
• [Message 3: quoting message 1] B: Me me me
• [Message 4: quoting message 2] C: I also got WA
• [Message 5: quoting message 2] B: Did you forget to use long long?
• [Message 6: quoting message 5] A: After changing it, I got AC. That's awesome!

For message $i$ ($1 \le i \le n$), A uses $r_i$ to mark whether message $i$ has a quote and the message number it quotes. If $r_i > 0$, then message $i$ quotes message $r_i$; if $r_i = 0$, then message $i$ quotes no message.

There are a lot of messages in the chat history. To quickly find the needed messages, A plans to implement a simple message search tool. At any moment, the tool can be positioned at exactly one message. If it is currently at message $i$ ($1 < i \le n$), then next you may choose one of the following two operations:

• Move to message $i - 1$.
• If message $i$ quotes message $r_i$, move to message $r_i$.

You may perform the operations any number of times (including zero times).

A has $q$ queries. In the $k$-th query ($1 \le k \le q$), A gives message numbers $x_k, y_k$ ($y_k < x_k$). A wants to know: if the tool is currently at $x_k$, what is the minimum number of operations needed to move to $y_k$.

Input Format

The first line contains two positive integers $n, q$, representing the number of messages and the number of queries.

The second line contains $n$ non-negative integers $r_1, r_2, \dots, r_n$, describing the quoting relationships. The meaning is as described above.

Each of the next $q$ lines, the $k$-th line ($1 \le k \le q$) contains two positive integers $x_k, y_k$, representing one query.

It is guaranteed that there are at most 1000 messages that contain quotes.

Output Format

Output $q$ lines. Each line contains one integer, representing the minimum number of operations needed to switch from message $x_k$ to message $y_k$.

6 3
0 0 1 2 2 5
4 1
6 2
6 3

2
2
3

5 5
0 0 0 1 3
4 1
4 2
5 1
5 2
5 3

1
2
2
2
1

Hint

Constraints

For $40\%$ of the test points, it is guaranteed that $1 \le n \le 2000$ and $1 \le q \le 2000$.

For all test points, it is guaranteed that $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$, and there are at most 1000 messages that contain quotes.

Translated by ChatGPT 5