Последовательность ДНК любого живого существа в Берляндии представима в виде непустой строки из маленьких латинских букв. Берляндские ученые выяснили, что эволюции всех существ происходят поэтапно. На одном этапе ровно один некоторый символ последовательности ДНК заменяется ровно на два других. При этом всего бывает n допустимых замен. Замена ai->bici означает, что можно заменить один любой символ ai на пару символов bici. Каждая замена могла произойти неограниченное число раз.
Говорят, что два существа, имеющие последовательности ДНК s1 и s2, могут иметь общего предка, если существует такая последовательноcть ДНК s3, что из нее в процессе эволюции могут быть получены s1 и s2, возможно за разное число этапов. По заданным s1 и s2 требуется определить, могут ли существа, имеющие такие последовательности ДНК, иметь общего предка. В случае положительного ответа требуется найти длину кратчайшей последовательноcти ДНК общего предка.
Выходные данные
Если s1 и s2 не могут иметь общего предка, выведите -1. Иначе выведите длину кратчайшей последовательности s3, из которой могли быть получены s1 и s2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
ababa
aba
2
c->ba
c->cc
|
2
|
|
2
|
ababa
aba
7
c->ba
c->cc
e->ab
z->ea
b->ba
d->dd
d->ab
|
1
|
|
3
|
ababa
aba
1
c->ba
|
-1
|