e-olymp
Problems

Relatives (RU)

Relatives (RU)

prb183 Кроме того, что имена орков невероятно выразительны, они еще могут сказать кое-что о родственных связях их обладателей. Например, если два орка носят имена, которые могут быть сделаны одинаковыми посредством удаления не более половины букв из каждого, то эти орки являются родственниками в первом колене. Так, например, orgrim и grom являются родственниками в первом колене, поскольку из первого имени могут быть удалены три буквы из шести (o,r,i), а из второго – одна из четырех (o), и тогда получатся одинаковые имена grm. Двое орков с именами A и B будут родственниками в (n+1)-ом колене, если существует такое имя C, что орки с именами A и C являются родственниками в 1 колене, а B и C – родственниками в n-ом колене. Нетрудно заметить, что если два орка являются родственниками в n-ом колене, то они являются родственниками и в любом колене m > n. Однако степень родства орков определяется наименьшим коленом, в котором они являются родственниками.

Напишите программу, которая для двух орков с заданными именами определяет степень n (n1) их родства.

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

Входной файл описывается двумя строками, состоящими из маленьких латинских букв и определяющих имена двух орков. Каждое имя состоит не менее чем из 1 буквы и не более чем из 100.

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

В выходной файл выведите степень n родства орков c заданными именами или строку "not related" (без кавычек), если данные два орка не являются родственниками в n-ом колене ни при каком n.

Time limit 1 second
Memory limit 64 MiB
Input example
Sample 1
orgrim
grom

Sample 2
a
b

Sample 3
goo
ogg
Output example
Sample 1
1


Sample 2
2


Sample 3
2