원형 패싱

시간 제한2초메모리 제한1024 MB

요약

2N명이 원형으로 서 있고 최고의 친구 쌍이 정반대에 서 있을 때, 각 질문마다 학생 x에서 y로 공을 전달하는 최소 패스 수를 구합니다.

난이도: 어려움10점 중 8점
유형: 그래프, 최단 경로, 수학
정답자: 아직 제출이 없습니다

문제

아네이크는 오늘 고등학교에 입학한 첫날입니다. 체육 선생님은 준비 운동으로 반 학생들에게 이름 익히기 게임을 시킵니다. 반에는 $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$ 은 학생 수, $M$ 은 단짝 쌍의 수, $Q$ 는 게임 수입니다.

둘째 줄에는 $M$ 개의 정수 $k_0, \ldots, k_{M-1}$ 이 주어집니다. 각 $i$ 에 대해 단짝은 위치 $k_i$ 와 $k_i+N$ 에 섭니다. 각 학생의 단짝은 최대 한 명입니다.

이후 $Q$ 줄에는 각각 두 정수 $x_i$ 와 $y_i$ 가 주어지며, 이는 게임 $i$ 에서 고른 두 학생입니다.

출력

$Q$ 줄을 출력합니다. $i$ 번째 줄에는 게임 $i$ 에서 필요한 최소 패스 횟수를 한 정수로 출력합니다.

제한

$2 \leq N \leq 5 \cdot 10^8$

$1 \leq M \leq 5 \cdot 10^5$ 이고 $M \le N$

$1 \leq Q \leq 2 \cdot 10^4$

$0 \leq k_0 < k_1 < \ldots < k_{M-1} < N$

$0 \leq x_i, y_i < 2N$ 이고 $x_i \neq y_i$

힌트

아래 두 그림은 첫 번째와 네 번째 예제의 배치를 보여 줍니다. 서로의 이름을 아는 두 학생은 간선으로 연결되어 있습니다.

첫 번째 예제의 첫 게임에서는 학생 $1$ 에게 공이 주어집니다. 학생 $1$ 은 단짝인 학생 $5$ 에게 공을 넘깁니다. 학생 $5$ 가 학생 $4$ 에게 넘기므로, 공은 총 두 번의 패스로 학생 $4$ 에게 도착합니다.

예제5

예제 1
입력
```
4 1 5
1
1 4
1 5
1 7
1 2
1 6
```
예상 출력
```
2
1
2
1
2
```
예제 2
입력
```
6 1 3
5
5 7
5 1
5 11
```
예상 출력
```
2
3
1
```
예제 3
입력
```
4 2 4
2 3
0 2
0 3
0 6
0 7
```
예상 출력
```
2
2
2
1
```

예제 4

입력

예상 출력

예제 5

입력

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

예상 출력

2210878
5876730
231106567