그대, 그머가 되어

선린에 합격한 대호에게는 큰 고민이 있다. 중학교 3년 내내 공부만 한 대호는 요즘 학생들이 쓰는 '야민정음'을 전혀 모른다. 친구들의 대화에 끼고 싶은 대호는 야민정음을 공부하기로 했다.

야민정음은 모양이 비슷한 글자를 원래 글자 대신 쓰는 것을 말한다. 예를 들어 '그대'는 '그머'로, '팔도비빔면'은 '괄도네넴댼'으로, '식용유'는 '식용윾'으로, '대호'는 '머호'로 바꿀 수 있다. 아무 글자나 바꿀 수 있는 것은 아니고, 서로 치환할 수 있는 글자 쌍이 정해져 있다. 한 쌍의 두 글자는 어느 쪽으로든 서로 바꿀 수 있다.

예를 들어 쌍 (a, b), (a, c), (b, d), (c, d)가 주어지면 a를 d로 바꾸는 방법은 a-b-d와 a-c-d의 2가지이다. 쌍 (a, b), (b, c), (a, c)가 주어지면 a를 c로 바꾸는 방법은 a-b-c와 a-c의 2가지인데, 이 경우에는 두 방법의 치환 횟수가 다르다.

머호는 글자 a를 글자 b로 바꾸려 한다. 글자는 $N$개, 치환할 수 있는 글자 쌍은 $M$개이다. a를 b로 바꾸는 데 필요한 치환의 최소 횟수를 구해 머호에게 알려 주자.

프로그램 작성의 편의를 위해 머호가 공부하는 모든 글자는 자연수로 주어진다.

첫째 줄에 머호가 바꾸려는 글자 a와 b가 주어진다.

둘째 줄에 전체 글자의 수 $N$과 치환할 수 있는 글자 쌍의 수 $M$이 주어진다. ($1 \le N \le 1\,000$, $1 \le M \le 10\,000$)

다음 $M$개의 줄에 치환할 수 있는 글자 쌍이 한 줄에 하나씩 주어진다. 모든 글자는 $N$ 이하의 자연수이다.

a를 b로 바꾸는 데 필요한 최소 치환 횟수를 출력한다. a와 b가 같으면 0을 출력한다. 치환이 불가능하면 -1을 출력한다.