| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 9 | 6 | 6 | 66.667% |
It is the first day of high school for Anouk; as a warm-up activity, her sports teacher is making the class play name-learning games. There are 2ドルN$ 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 of the students in a circle, consecutively assigning each student a number from 0ドル$ to 2ドルN - 1$. More specifically, for each 0ドル \leq i < 2N - 1,ドル students $i$ and $i + 1$ stand next to each other. Additionally, students 0ドル$ and 2ドルN - 1$ stand next to each other.
Since the teacher wants everyone to meet new students, best friends have to stand as far away from each other as possible, i.e. opposite each other. That is, the students forming the $i$th pair of best friends are standing at positions $k_i$ and $k_i + N$ respectively, where 0ドル \leq k_i < N$.
The teacher selects two students $x$ and $y$ and hands a ball to student $x$. The goal is to send 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 rules were explained, each student got to know the names of the two students standing directly beside them. Other than that, no one knows any other names.
The game is played $Q$ times; the teacher chooses two students each time. Since the students are not paying attention, they do not learn any new names throughout the games. What is the minimum number of passes needed to get the ball from student $x$ to student $y$ in each game?
The first line of input contains three integers, $N,ドル $M$ and $Q,ドル where 2ドルN$ 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 that are played.
The second line contains $M$ integers $k_0, \ldots, k_{M-1},ドル with $k_i$ describing the $i$th pair of best friends. For each $i,ドル the best friends stand at positions $k_i$ and $k_i + N$ respectively. Each student has at most one best friend.
The following $Q$ lines each contain two integers, $x_i$ and $y_i,ドル the two selected students in game $i$.
Output $Q$ lines, the $i$th line containing a single integer, the minimum number of passes needed in game $i$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 14 | $M = 1$ and $x_i = k_0$. In other words, there is a single pair of best friends, and in every game, the student starting with the ball has a best friend. |
| 2 | 20 | $N,M,Q \leq 1000$ |
| 3 | 22 | $N \leq 10^7$ and $M,Q\leq 1000$ |
| 4 | 17 | $x_i = 0$ for all $i$ |
| 5 | 27 | No additional constraints |
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
The following two figures depict the arrangements in the first and the fourth sample. Two students are connected by an edge if they know each other's names.
In the first game of the first sample, the ball is given to student 1ドル$. Student 1ドル$ passes the ball to their best friend, student 5ドル$. The ball reaches student 4ドル$ after student 5ドル$ passes it to them, needing two passes in total.