Manobras autorizadas
Uma fila de vagões é descrita por uma string . Cada letra minúscula identifica um tipo de vagão. Queremos obter a sequência de tipos descrita por outra string de mesmo comprimento.
Uma manobra troca dois vagões vizinhos. Ela só é permitida quando seus tipos são diferentes e o par de tipos está na lista de autorizações; a autorização vale nas duas direções. Vagões do mesmo tipo são indistinguíveis para o objetivo.
Determine a menor quantidade de manobras necessária, ou informe que a transformação é impossível.
Input
A primeira linha contém (; ). As duas próximas linhas contêm e , cada uma com exatamente letras de a a z. Não é garantido que possuam as mesmas quantidades de cada letra.
As próximas linhas contêm duas letras distintas. Nenhum par não ordenado se repete.
Output
Imprima o mínimo de manobras, ou -1 se não for possível.
Samples
Sample 1
Input
4 2 abac baac a b a c
Output
1
Troque os dois primeiros vagões.
Sample 2
Input
3 1 abc cba a c
Output
-1
O vagão do tipo b não pode trocar de posição com seus vizinhos, impedindo a transformação.