When Geudae Becomes Geumeo

Daeho has just been admitted to Sunrin, and he has a big problem. He spent all three years of middle school studying, so he knows nothing about 'Yamin Jeongeum', the slang today's students use. Daeho wants to join his friends' conversations, so he decides to study it.

Yamin Jeongeum is the practice of writing a character with a similar shape in place of the original character. For example, '그대' can become '그머', '팔도비빔면' can become '괄도네넴댼', '식용유' can become '식용윾', and '대호' can become '머호'. Not every character can be replaced: a fixed set of character pairs can be substituted for each other. The two characters of a pair can be swapped in either direction.

For example, if the pairs (a, b), (a, c), (b, d), (c, d) are given, there are 2 ways to turn a into d: a-b-d and a-c-d. If the pairs (a, b), (b, c), (a, c) are given, there are 2 ways to turn a into c: a-b-c and a-c. In this case the two ways use a different number of substitutions.

Meoho (the Yamin Jeongeum form of Daeho) wants to turn character a into character b. There are $N$ characters and $M$ substitutable pairs. Find the minimum number of substitutions needed to turn a into b and tell Meoho.

To make programming easier, every character Meoho studies is given as a natural number.

The first line contains the characters a and b that Meoho wants to convert from and to.

The second line contains the total number of characters $N$ and the number of substitutable pairs $M$. ($1 \le N \le 1\,000$, $1 \le M \le 10\,000$)

Each of the next $M$ lines contains one substitutable pair. Every character is a natural number not greater than $N$.

Print the minimum number of substitutions needed to turn a into b. If a and b are the same, print 0. If the conversion is impossible, print -1.