eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Родственники

Родственники

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
prb183

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

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

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

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

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

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

Пример

Входные данные #1
orgrim
grom
Выходные данные #1
1