E. Общий предок
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Последовательность ДНК любого живого существа в Берляндии представима в виде непустой строки из маленьких латинских букв. Берляндские ученые выяснили, что эволюции всех существ происходят поэтапно. На одном этапе ровно один некоторый символ последовательности ДНК заменяется ровно на два других. При этом всего бывает n допустимых замен. Замена ai->bici означает, что можно заменить один любой символ ai на пару символов bici. Каждая замена могла произойти неограниченное число раз.

Говорят, что два существа, имеющие последовательности ДНК s1 и s2, могут иметь общего предка, если существует такая последовательноcть ДНК s3, что из нее в процессе эволюции могут быть получены s1 и s2, возможно за разное число этапов. По заданным s1 и s2 требуется определить, могут ли существа, имеющие такие последовательности ДНК, иметь общего предка. В случае положительного ответа требуется найти длину кратчайшей последовательноcти ДНК общего предка.

Входные данные

В первой строке записана непустая последовательность ДНК s1, во второй строке записана непустая последовательность ДНК s2. Длины этих строк не превосходят 50, строки содержат только маленькие латинские буквы. В третьей строке записано целое число n (0 ≤ n ≤ 50) — допустимых замен. Далее следует n строк, каждая из которых описывает очередную замену в формате ai->bici. Символы ai, bi, и ci — маленькие латинские буквы. Строки s1 и s2 могут совпадать, список замен может содержать одинаковые замены.

Выходные данные

Если s1 и s2 не могут иметь общего предка, выведите -1. Иначе выведите длину кратчайшей последовательности s3, из которой могли быть получены s1 и s2.

Примеры
Входные данные
ababa
aba
2
c->ba
c->cc
Выходные данные
2
Входные данные
ababa
aba
7
c->ba
c->cc
e->ab
z->ea
b->ba
d->dd
d->ab
Выходные данные
1
Входные данные
ababa
aba
1
c->ba
Выходные данные
-1