매일의 통학
시간 제한1초메모리 제한1024 MB
지하철 노선 순열에서 교환이 일어날 때마다 열차와 W개의 단방향 통로를 이용해 1번 역에서 N번 역까지 가는 최소 시간을 구한다.
문제
토론토에는 1번부터 N번까지 번호가 붙은 N개의 지하철역이 있다. 당신은 1번 역에서 출발해서, 매일 N번 역에 도착해야 학교에 갈 수 있다.
역들 사이에는 W개의 단방향 통로가 있고, i번째 통로를 이용하면 역 Ai에서 다른 역 Bi (1 ≤ Ai, Bi ≤ N, Ai ≠ Bi)까지 1분 만에 걸어갈 수 있다. 같은 두 역을 잇는 통로가 여러 개 있을 수도 있다.
지하철 노선은 1번 역에서 시작해서 N개의 역을 한 번씩 방문하는 정해진 경로를 따른다. 처음에는 이 경로가 S1, S2, ..., SN 순서이다. S1 = 1이고, S2, . . . , SN은 2, . . . , N을 나열한 순열이다. 이 경로를 따라 하루에 지하철 한 대만 운행하는데, 오전 6시에 1번 역에서 출발해서 다음 역까지 가는 데 각각 1분이 걸린다. 즉, 오전 6시로부터 m분이 지나면 지하철은 역 Sm+1에 있다 (m ≥ N − 1이면 역 SN에 있다).
그런데 D일에 걸쳐 지하철 노선의 경로가 계속 바뀐다. i번째 날이 시작될 때, 경로의 Xi번째 역과 Yi번째 역 (2 ≤ Xi, Yi ≤ N, Xi ≠ Yi)이 서로 교환된다. 이런 변경이 있은 뒤에도 경로는 여전히 1번 역에서 시작하고 N개의 역을 모두 한 번씩 방문한다. 변경은 다음 날로 이어지며, 경로가 S1, . . . , SN으로 저절로 되돌아가지는 않는다.
이 D일 각각에 대해, 당신은 얼마나 빨리 학교에 도착할 수 있는지 알고 싶다. i번째 날에는 (지하철 노선의 i번째 변경이 있은 뒤) 오전 6시에 N번 역으로 가는 여정을 시작한다. 매분 당신은 지하철을 타고 다음 역으로 갈 수도 있고 (지금 있는 역에 지하철이 있고 아직 경로를 다 끝내지 않았을 때), 현재 역에서 통로를 따라 다른 역으로 걸어갈 수도 있고, 현재 역에서 기다릴 수도 있다. 여정은 지하철 운행과 같은 시각에 시작하므로, 원한다면 곧바로 지하철을 탈 수 있고, 도중에 내렸다가 다시 탈 수도 있다.
입력
첫째 줄에 공백으로 구분된 세 정수 N, W, D가 주어진다.
다음 W개 줄에는 각각 공백으로 구분된 두 정수 Ai, Bi (1 ≤ i ≤ W)가 주어진다.
다음 줄에는 공백으로 구분된 N개의 정수 S1, . . . , SN이 주어지며, 이는 역들의 초기 순열이다.
다음 D개 줄에는 각각 공백으로 구분된 두 정수 Xi, Yi (1 ≤ i ≤ D)가 주어진다.
출력
D개 줄을 출력하며, 한 줄에 정수 하나씩 출력한다. i번째 줄은 i번째 날에 N번 역에 도착하는 데 필요한 최소 분 수이다 (1 ≤ i ≤ D).
제한
- 3 ≤ N ≤ 200 000
- 0 ≤ W ≤ 200 000
- 1 ≤ D ≤ 200 000