156. Опечатки

(эпиграф)(с одного форума)

— Кто сочинил эту чушь?

— Астрофизики. Они тоже люди.

— Вы 10 ошибок в слове журналисты сделали.

Многие пользователи делают ошибки при наборе, некоторые — из-за попаданий мимо клавиш, некоторые — из-за своей неграмотности. Мы хотим проверить, мог ли пользователь на самом деле иметь в виду некоторое другое слово, чем то, которое он набрал.

Более формально, предположим, что имеет место следующая модель ошибок: пользователь начинает с некоторого слова, которое он хочет написать, и дальше последовательно делает в нём некоторое количество ошибок. Каждая ошибка представляет собой замену некоторой подстроки слова на другую подстроку. Одно ошибка соответствует замене только в одной позиции (то есть если пользователь захочет сделать единственную ошибку по правилу abc -> cba, то из строки abcabc он может получить либо cbaabc, либо abccba. После каждой ошибки процесс повторяется. Одно и то же правило могло использоваться несколько раз в различных шагах (так, в вышеприведённом примере за два шага могло получиться cbacba).

Требуется определить, какое минимальное количество ошибок пользователь мог совершить, если он имел в виду одно заданное слово, а написал — другое.

В первой строке содержится слово, которое по нашему предположению пользователь имел в виду (оно состоит из букв латинского алфавита в нижнем регистре, длина не превышает 20).

Во второй строке содержится слово, которое он на самом деле написал (оно также состоит из букв латинского алфавита в нижнем регистре, длина не превышает 20).

В третьей строке содержится единственное число $N$ ($N \le 50$) — количество замен, описывающих различные ошибки.

В следующих $N$ строках содержатся возможные замены в формате <правильная последовательность букв><пробел><ошибочная последовательность букв>.

Последовательности имеют длину не более 6 символов.

Требуется вывести одно число — минимальное количество ошибок, которое мог совершить пользователь. Если это количество превышает 4, или же из одного слова невозможно получить другое, следует вывести -1.