P10848 [EGOI 2024] Circle Passing / Ball Passing Game

Day 2 Problem A. The statement is translated from [EGOI2024 circlepassing](https://wiki.egoi2024.nl/tasks/circlepassing/statement-isc.pdf). The translation comes from [ChatGPT](https://chatgpt.com/) and has been manually proofread. If there are any mistakes, please contact [rui_er](https://www.luogu.com.cn/user/122461).

This is Anouk’s first day at high school. As a warm-up activity, her PE teacher has the class play a game to remember names. There are $2N$ students in the class. Most of them do not know each other, but there are $M$ pairs of best friends who do everything together. Each student has at most one best friend. The teacher arranges all students in a circle and assigns each student a consecutive number from $0$ to $2N - 1$. More specifically, for each $0 \le i < 2N - 1$, students $i$ and $i + 1$ stand next to each other. Also, students $0$ and $2N - 1$ stand next to each other. Since the teacher wants everyone to meet new classmates, best friends must be as far apart as possible, i.e., they stand opposite each other. That is, the students forming the $i$-th pair of best friends stand at positions $k_i$ and $k_i + N$, where $0 \le k_i < N$. The teacher chooses two students $x$ and $y$ and gives a ball to student $x$. The goal is to pass the ball to student $y$, but each student may only pass the ball to another student whose name they already know. Of course, best friends know each other’s names. While the teacher explains the rules, each student learns the names of the two students standing directly next to them. Other than that, nobody knows anyone else’s name. The game is played $Q$ times. Each time, the teacher chooses two students. Since the students are not paying attention, they do not learn any new names during the games. In each game, what is the minimum number of passes needed to get the ball from student $x$ to student $y$?

The first line contains three integers $N$, $M$, and $Q$, where $2N$ is the number of students in Anouk’s class, $M$ is the number of pairs of best friends, and $Q$ is the number of games played. The second line contains $M$ integers $k_0,\cdots,k_{M-1}$, where $k_i$ describes the $i$-th pair of best friends. For each $i$, the best friends stand at positions $k_i$ and $k_i + N$. Each student has at most one best friend. The next $Q$ lines each contain two integers $x_i$ and $y_i$, the two students chosen in the $i$-th game.

Output $Q$ lines. The $i$-th line should contain one integer, the minimum number of passes needed in the $i$-th game.

**Sample Explanation** The following two figures show the arrangements for Sample 1 and Sample 4. If two students know each other, there is an edge connecting them.  In the first query of Sample 1, the ball is passed to student $1$. Student $1$ passes the ball to their best friend, student $5$. After student $5$ passes the ball to student $4$, the ball reaches student $4$. In total, it takes two passes. --- **Constraints** For all testdata, $2\le N\le 5\times 10^8$, $1\le M\le 5\times 10^5$ and $M\le N$, $1\le Q\le 2\times 10^4$, $0\le k_0