시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 14 8 7 63.636%

문제

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

도로 네트워크는 길이가 M인 두 수열 A와 B로 나타낼 수 있다. 두 도시 (X, Y)사이에 단방향도로가 있으려면, Ai가 X의 약수이면서, Bi가 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 ≤ 109, 1 ≤ S, T ≤ N, 1 ≤ M ≤ 1,000)

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

출력

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

예제 입력 1

11 9 6 2
3 10
5 2

예제 출력 1

2

예제 입력 2

123456789 18 12 3
1 42 50
1 17 3

예제 출력 2

1

예제 입력 3

60 30 8 3
16 15 12
2 20 5

예제 출력 3

-1

예제 입력 4

77 10 62 6
2 5 7 4 17 26
25 7 11 13 31 34

예제 출력 4

4

힌트

예제 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의 경우에 A0 = B0 = 1이기 때문에, 모든 도시 사이에 도로가 존재한다.

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

출처