14207번 - 약수 도로

N개의 도시로 이루어진 나라고 있다. 도시는 1번부터 N번까지 번호가 매겨져 있다. 일부 두 도시는 단위길이의 단방향 도로로 연결되어져 있다. 도시 X에서 Y로 가는 거리는 X에서 Y로 가는데 필요한 도로 개수의 최솟값이다.

도로 네트워크는 길이가 M인 두 수열 A와 B로 나타낼 수 있다. 두 도시 (X, Y)사이에 단방향도로가 있으려면, A_i가 X의 약수이면서, B_i가 Y의 약수인 i가 적어도 하나 존재해야 한다.

예를 들어, 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 ≤ N ≤ 10⁹, 1 ≤ S, T ≤ N, 1 ≤ M ≤ 1,000)

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

첫째 줄에 S에서 T로 가는 거리를 출력한다. 만약, 갈 수 없는 경우에는 -1을 출력한다.

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

예제 2의 경우에 A₀ = B₀ = 1이기 때문에, 모든 도시 사이에 도로가 존재한다.

예제 4의 경우에 최단 경로는 10 -> 56 -> 26 -> 34 -> 62 이다.