약수 도로

N개의 도시로 이루어진 나라가 있다. 도시에는 1번부터 N번까지 번호가 붙어 있고, 일부 도시 쌍은 길이가 1인 단방향 도로로 이어져 있다. 도시 X에서 Y로 가는 거리는 X에서 출발해 Y에 도착하기까지 지나는 도로 개수의 최솟값이다.

도로망은 길이가 M인 두 수열 A와 B가 결정한다. $A_i$가 X의 약수이고 $B_i$가 Y의 약수인 i가 하나 이상 있으면, 그리고 그때만 X에서 Y로 가는 단방향 도로가 있다.

예를 들어 $N = 7$, $M = 1$, $A = [2]$, $B = [3]$이면 도시는 7개이고 도로는 2 -> 3, 2 -> 6, 4 -> 3, 4 -> 6, 6 -> 3, 6 -> 6이다.

두 정수 S와 T가 주어졌을 때, S에서 T로 가는 거리를 구하는 프로그램을 작성하시오.

첫째 줄에 N, S, T, M이 주어진다. ($2 \le N \le 10^9$, $1 \le S, T \le N$, $1 \le M \le 1000$)

둘째 줄에 수열 A가, 셋째 줄에 수열 B가 주어진다. ($1 \le A_i, B_i \le N$) 같은 $(A_i, B_i)$ 쌍이 두 번 이상 주어지는 경우는 없다.

첫째 줄에 S에서 T로 가는 거리를 출력한다. T로 갈 수 없으면 -1을 출력한다.

첫 번째 예제의 도로는 (3, 5), (3, 10), (6, 5), (6, 10), (9, 5), (9, 10), (10, 2), (10, 4), (10, 6), (10, 8), (10, 10)이다. 도시 9에서 6으로 가는 최단 경로는 9 -> 10 -> 6이다.

두 번째 예제는 A와 B의 첫 원소가 모두 1이라서 모든 도시 사이에 도로가 있다.

네 번째 예제의 최단 경로는 10 -> 56 -> 26 -> 34 -> 62이다.