P15804 [GESP202603 Level 8] Message Search

Related multiple-choice and true/false problems: .

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$.

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 $q$ lines. Each line contains one integer, representing the minimum number of operations needed to switch from message $x_k$ to message $y_k$.

### 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