背景

Day 2 Problem A.

题面译自 EGOI2024 circlepassing。翻译来自于 ChatGPT 并进行人工校对，若有误请联系 rui_er。

题目描述

这是 Anouk 高中的第一天；作为热身活动，她的体育老师让班级玩记忆名字的游戏。班上有 $2N$ 名学生。他们中的大多数人彼此不认识，但有 $M$ 对最好的朋友，他们一起做任何事情。每个学生最多有一个最好的朋友。

老师把所有学生安排成一个圆圈，连续给每个学生分配一个从 $0$ 到 $2N - 1$ 的编号。更具体地，对于每个 $0 \le i < 2N - 1$，学生 $i$ 和 $i + 1$ 站在一起。此外，学生 $0$ 和 $2N - 1$ 也站在一起。

由于老师希望每个人都能结识新同学，所以最好的朋友必须尽可能远离彼此，即相对而站。也就是说，形成第 $i$ 对好朋友的学生分别站在位置 $k_i$ 和 $k_i + N$，其中 $0 \le k_i < N$。

老师选择了两个学生 $x$ 和 $y$ 并将一个球交给学生 $x$。目标是将球传给学生 $y$，但每个学生只能将球传给另一个他们已经知道名字的学生。当然，最好的朋友彼此知道对方的名字。在老师解释规则期间，每个学生都认识了直接站在他们旁边的两个学生的名字。除此之外，没有人知道其他人的名字。

游戏玩了 $Q$ 次；每次老师选择两个学生。由于学生们没有注意，他们在游戏过程中不会学到任何新名字。在每场游戏中，从学生 $x$ 到学生 $y$ 需要的最少传球次数是多少？

输入格式

输入的第一行包含三个整数，$N, M$ 和 $Q$，其中 $2N$ 是 Anouk 班上的学生数，$M$ 是最好朋友的对数，$Q$ 是进行的游戏次数。

第二行包含 $M$ 个整数 $k_0 ,\cdots, k_{M-1}$，其中 $k_i$ 描述了第 $i$ 对好朋友。对于每个 $i$，最好朋友分别站在位置 $k$ 和 $k + N$。每个学生最多有一个最好的朋友。

接下来的 $Q$ 行每行包含两个整数，$x_i$ 和 $y_i$，即第 $i$ 场游戏中选择的两个学生。

输出格式

输出 $Q$ 行，第 $i$ 行包含一个整数，即第 $i$ 场游戏中所需的最少传球次数。

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

提示

样例解释

以下两图描述了第一个样例和第四个样例中的排列情况。如果两个学生彼此认识，他们之间就有一条边连接。

在第一个样例的第一个游戏中，球被传给学生 $1$。学生 $1$ 将球传给他们的好朋友学生 $5$。球在学生 $5$ 传给学生 $4$ 后到达学生 $4$，总共需要两次传球。

数据范围

对于全部数据，$2\le N\le 5\times 10^8$，$1\le M\le 5\times 10^5$ 且 $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$ 且 $x_i\ne y_i$。

• 子任务一（$14$ 分）：$M=1$ 且 $x_i=k_0$。换句话说，仅有一对最好的朋友，且在每局游戏中，最开始有球的人有一个最好的朋友。
• 子任务二（$20$ 分）：$N,M,Q\le 1000$。
• 子任务三（$22$ 分）：$N\le 10^7$ 且 $M,Q\le 1000$。
• 子任务四（$17$ 分）：$x_i=0$。
• 子任务五（$27$ 分）：无特殊限制。

注：部分测试点在 EGOI 中被放在多个子任务中。为节省评测资源及整理数据的工作量，这些测试点被放在包含它的所有子任务中编号最小的一个。这可能导致一份代码得到比预期更高的分数，但是无法过题。