Маньяк

면접 대비

메모리 제한1024 MB

요약
알파벳의 각 문자를 다른 문자로 보내는 함수 f가 주어질 때, 첫 번째 문자열에 f를 반복 적용해 두 번째 문자열과 같아지게 하는 최소 횟수를 구하고, 불가능하면 -1을 출력한다.
난이도

보통10점 중 6점

유형
문자열, 그래프, 시뮬레이션, 구현
정답자
아직 제출이 없습니다

문제

Недавно в городе появился маньяк. И Шерлок как обычно решил взяться за дело. На каждой жертве, найденной детективом Лестрейдом, доктор Ватсон обнаружил символ латинского алфавита. Применив свой метод дедукции и добавив к нему чуть-чуть интуиции, Шерлок увидел, что все имена жертв начинаются с разных букв. Всего было 26 жертв, поэтому для каждого символа латинского алфавита --- первой буквы имени жертвы --- он сопоставил символ, который был обнаружен на теле этой жертвы. Таким образом Шерлок провел соответствие между символами алфавита. Здесь и дальше будем говорить, что f(c)f(c) --- символ, сопоставленный символу cc, где cc --- один из символов латинского алфавита.

Когда сыщик уже практически потерял надежду разрешить эту головоломку, ему пришло письмо от этого самого маньяка. В этом письме были всего лишь две строки одинаковой длины, и никакого пояснения о том, что с ними делать. Немного поразмыслив, Шерлок понял, что для разрешения загадки ему необходимо посчитать следующую величину: количество раз, которое ему необходимо заменить все символы первой строки (каждый символ cc заменяется на f(c)f(c)), чтобы получить вторую строку.

Поскольку Шерлок не хочет нагружать голову лишней информацией, он обратился к Вам за помощью. Помогите ему!

입력

В первой строке входного файла даны 26 символов. kk-й символ этой строки показывает, какой символ соответствует kk-му символу латинского алфавита.

Во второй строке дано число nn (1≤n≤1,000,0001 \le n \le 1\\,000\\,000) --- длина строк, присланных маньяком.

В каждой из следующих двух строк записана строка длиной nn, состоящая из строчных латинских символов.

Символы латинского алфавита нумеруются с единицы, начиная с символа a и заканчивая символом z.

출력

В единственной строке выходного файла выведите необходимое количество операций замены символов.

Если ответа не существует, выведите -1.

힌트

В тесте из примера первая строка будет меняться следующим образом:

  • После первой замены всех символов строка abacaba превратится в строку bcbdbcb (символ a заменяется на b, b --- на c, c --- на d)
  • После второй замены всех символов уже новая строка bcbdbcb превратится в cdcecdc (символ b заменяется на c, c --- на d, d --- на e)
  • То есть после двух замен всех символов мы получили вторую строку, значит ответ равен 2

예제1

  1. 예제 1

    입력
    bcdefghijklmnopqrstuvwwwww
7
abacaba
cdcecdc
    예상 출력
    2