재귀 회로

재귀적인 초소형 회로의 배치에는 접점이 전부 $N$개 있고, 그중 일부 접점 쌍은 도전성 경로로 직접 연결되어 있습니다. 이 회로에는 $S$개의 하위 회로도 있으며, 각 하위 회로는 이 회로와 완전히 같은 복사본입니다.

회로 배치의 접점은 세 종류입니다.

1. 회로의 입력 접점($K$개). 회로를 외부 도전성 경로와 잇는 유일한 접점입니다.
2. 중첩된 하위 회로의 입력 접점($S \cdot K$개).
3. 보조 접점.

이 접점들은 모두 제약 없이 도전성 경로로 서로 연결할 수 있습니다.

신호는 도전성 경로를 따라 이동합니다. 신호가 접점에 도달하면 그 접점에 연결된 경로 중 어느 것이든 따라갈 수 있습니다. 외부 신호가 하위 회로의 입력 접점에 도달하면 그 하위 회로 안으로 들어가 내부 경로를 따라 더 이동할 수 있습니다. 내부 신호가 하위 회로의 입력 접점에 도달하면 하위 회로 밖으로 나가 회로 바깥 경로를 따라 이동할 수 있습니다(바깥에 경로가 있고, 바깥 회로 자체가 다른 회로의 하위 회로인 경우에 한합니다).

가장 바깥 회로를 생각하며, 그 바깥에는 아무것도 없다고 합니다. 회로의 지정된 두 입력 접점이 경로로 연결되어 있는지 판정하십시오. 신호가 한쪽 접점에서 다른 쪽 접점으로 도달할 수 있으면 두 접점은 연결된 것입니다. 이때 신호는 여러 하위 회로에 유한한 횟수만큼 들어갈 수 있습니다.

연결 여부와 함께, 한 접점에서 다른 접점으로 가기 위해 신호가 하위 회로 안으로 얼마나 깊이 들어가야 하는지도 구하십시오. 가장 바깥 회로의 중첩 깊이는 0이고, 그 하위 회로의 깊이는 1, 그 하위 회로의 하위 회로는 2이며 이런 식입니다. 신호 경로마다, 신호가 지나가는 도전성 경로가 속한 회로들의 중첩 깊이 중 최댓값을 임계 깊이라고 합니다. 가장 바깥 회로의 두 지정된 입력 접점 사이 경로들에 대해 임계 깊이의 최솟값을 구하십시오.

첫 줄에 정수 네 개 $N$(배치의 접점 수), $K$(회로의 입력 접점 수), $S$(하위 회로 수), $M$(도전성 경로 수)이 주어집니다($1 \le K \le 100000$, $0 \le S \le 1000$, $K (S + 1) \le N \le 100000$, $0 \le M \le 100000$).

이어지는 $M$개의 줄에는 각각 경로로 직접 연결된 두 접점의 번호 $a$와 $b$가 주어집니다($1 \le a \neq b \le N$).

접점은 1부터 $N$까지 번호가 매겨져 있습니다. 회로의 입력 접점은 1부터 $K$까지 번호가 매겨져 있습니다. $t$번째 하위 회로의 입력 접점은 $tK + 1$부터 $tK + K$까지 번호가 매겨져 있습니다($1 \le t \le S$). $t$번째 하위 회로의 $j$번째 입력 접점은 바깥 회로 배치의 $(tK + j)$번째 접점입니다. 나머지 접점이 있다면 보조 접점입니다.

다음 줄에는 질의 수 $Q$가 주어집니다($1 \le Q \le 100000$). 이어지는 $Q$개의 줄에는 각각 가장 바깥 회로의 입력 접점 번호 $u$와 $v$가 주어집니다($1 \le u \neq v \le K$).

$Q$개의 정수를 한 줄에 하나씩 출력하십시오. $r$번째 수는 $r$번째 질의에서 한 입력 접점에서 다른 입력 접점으로 가는 데 필요한 중첩 깊이입니다. 다른 입력 접점에 도달할 수 없으면 깊이 대신 $-1$을 출력하십시오.