Problem Background

Day 2 Problem A.

The problem statement is translated from EGOI2024 circlepassing. The translation was done using ChatGPT and manually proofread. If there are any errors, please contact rui_er.

Problem Description

It's the first day at Anouk's high school; as a warm-up activity, her physical education 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 the students in a circle and assigns each student a number from $0$ to $2N - 1$ consecutively. More specifically, for each $0 \le i < 2N - 1$, student $i$ stands next to student $i + 1$. Additionally, student $0$ stands next to student $2N - 1$.

Since the teacher wants everyone to meet new classmates, best friends must be as far apart as possible, i.e., facing 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 selects two students $x$ and $y$ and hands the ball to student $x$. The goal is to pass the ball to student $y$, but each student can only pass the ball to another student whose name they already know. Of course, best friends know each other's names. During the teacher's explanation of the rules, each student learns the names of the two students directly standing next to them. Beyond that, no one knows anyone else's name.

The game is played $Q$ times; each time the teacher selects two students. Since the students are not paying attention, they do not learn any new names during the game. In each game, what is the minimum number of passes required from student $x$ to student $y$?

Input Format

The first line of input 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$ and $k + 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 selected in the $i$-th game.

Output Format

Output $Q$ lines, the $i$-th line containing a single integer, the minimum number of passes required in the $i$-th game.

Sample Input and Output

Input Sample #1

4 1 5
1
1 4
1 5
1 7
1 2
1 6

Output Sample #1

2
1
2
1
2

Input Sample #2

6 1 3
5
5 7
5 1
5 11

Output Sample #2

2
3
1

Input Sample #3

4 2 4
2 3
0 2
0 3
0 6
0 7

Output Sample #3

2
2
2
1

Input Sample #4

5 2 5
0 4
0 9
1 8
8 3
1 6
3 9

Output Sample #4

1
3
3
3
2

Input Sample #5

500000000 4 3
543234 1234566 2300001 249999999
2334445 123567
6578996 12455726
3 269979899

Output Sample #5

2210878
5876730
231106567

Notes

Sample Explanation

The following two diagrams describe the arrangements in the first and fourth samples. If two students know each other, there is an edge connecting them.

In the first game of the first sample, the ball is passed to student $1$. Student $1$ passes the ball to their best friend student $5$. The ball then reaches student $4$ after being passed by student $5$, requiring a total of two passes.

Data Range

For all data, $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 < k_1 < \cdots < k_{M-1} < N$, $0 \le x_i, y_i < 2N$ and $x_i \ne y_i$.

• Subtask 1 (14 points): $M = 1$ and $x_i = k_0$. In other words, there is only one pair of best friends, and in each game, the student initially holding the ball has a best friend.
• Subtask 2 (20 points): $N, M, Q \le 1000$.
• Subtask 3 (22 points): $N \le 10^7$ and $M, Q \le 1000$.
• Subtask 4 (17 points): $x_i = 0$.
• Subtask 5 (27 points): No special restrictions.

Note: Some test cases are used in multiple subtasks during EGOI. To save evaluation resources and simplify data management, these test cases are included in the subtask with the smallest number that contains them. This may result in a code receiving a higher score than expected, but it will not allow the code to pass the problem.

见题面 Input 部分

见题面 Output 部分