Background

Day 2 Problem A.

The statement is translated from EGOI2024 circlepassing. The translation comes from ChatGPT and has been manually proofread. If there are any mistakes, please contact rui_er.

Problem Description

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

Input Format

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 Format

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

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

2
1
2
1
2

6 1 3
5
5 7
5 1
5 11

2
3
1

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

2
2
2
1

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

1
3
3
3
2

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

2210878
5876730
231106567

Hint

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<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 every game, the student who starts with 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 additional constraints.

Note: Some test points were included in multiple subtasks in EGOI. To save judging resources and effort in organizing the data, these test points are placed in the subtask with the smallest index among all subtasks that contain them. This may cause a solution to get a higher score than expected, but still not pass the problem.

Translated by ChatGPT 5