Regra dos seis apertos de mão

A regra dos seis apertos de mão originada por Frigyes Karinthy, sugere que qualquer pessoa do mundo está conectada com qualquer outra através de seus contatos. Segundo ele o número máximo de elos que uma pessoa precisa para se conectar com qualquer outra é seis.

Ao se deparar com essa regra, Êda ficou curiosa para saber o número mínimo de elos que duas pessoas precisam para se conectar. Mas seria impossível calcular isso manualmente, já que existem bilhões de pessoas no mundo. Êda foi atrás do(a) melhor programador(a) que ela conhece para ajudá-la nesta tarefa, você.

Ajude Êda escrevendo um programa que permita escolher duas pessoas e determine o número mínimo de apertos de mão necessários para conectá-las.

Entrada

A entrada é composta por um único caso de teste. A primeira linha de um caso de teste contém 2 nomes $S$, o nome da primeira pessoa, e $E$, o nome da segunda pessoa que queremos verificar a conectividade.

A segunda linha contém 2 inteiros $N$ ($2 \leq N < 1000$), a quantidade de pessoas, e $M$ ($1 \leq M < N(N-1)/2$), a quantidade de apertos de mão.

Cada uma das $N$ linhas seguintes contém um nome $I$, representando o nome de cada uma das $N$ pessoas, onde o nome é composto por no máximo $25$ letras minúsculas e sem espaços.

As próximas $M$ linhas contém $2$ nomes $V$ e $W$, informando que a pessoa $V$ apertou a mão da pessoa $W$.

Saída

Imprima a quantidade mínima de apertos de mão necessários para conectar as pessoas $S$ e $E$. Caso não haja conexão entre as duas pessoas imprima -1.

Exemplo

Exemplo de entrada 1

alex eda
5 7
alex
barbara
carlos
duda
eda
alex carlos
barbara eda
alex duda
barbara alex
eda duda
duda barbara
carlos duda

Saída para o exemplo 1

2

No exemplo acima existem algumas conexões possíveis com 2 apertos de mão mas nenhuma com menos, segue algumas possibilidades que resultam em 2 apertos de mão:

• alex -> duda -> eda
• alex -> barbara -> eda

Exemplo de entrada 2

alex eda
6 8
alex
barbara
carlos
duda
eda
fabricio
alex carlos
barbara fabricio
alex duda
barbara alex
duda barbara
fabricio duda
carlos duda
fabricio carlos

Saída para o exemplo 2

-1

Neste exemplo não existe conexão entre as duas pessoas selecionadas