D. Расшифровка сигнала
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Штаб-квартира полиции отслеживает сигналы на разных частотах. Недавно они записали две подозрительные строки, s1 и s2, на двух частотах. Полиция подозревает, что эти две строки принадлежат двум преступникам, планирующим сделать какое-то злое деяние.

Поэтому полиция пытается найти общую подстроку этих двух строк. Искомая подстрока должна быть уникальной в первой строке и во второй строке. Другими словами, она должна встречаться ровно один раз в первой строке и ровно один раз во второй строке. Среди всех таких строк, полицию интересует строка с минимальной длиной.

Вам даны две строки, s1 и s2, состоящие из строчных букв латинского алфавита. Чему равна длина минимальной по длине общей уникальной подстроки строк s1 и s2? Формальное определение подстроки и уникальности смотрите в примечании.

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

В первой строке записана строка s1, а во второй строке записана строка s2 (1 ≤ |s1|, |s2| ≤ 5000). Обе строки состоят из строчных букв латинского алфавита.

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

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

Примеры
Входные данные
apple
pepperoni
Выходные данные
2
Входные данные
lover
driver
Выходные данные
1
Входные данные
bidhan
roy
Выходные данные
-1
Входные данные
testsetses
teeptes
Выходные данные
3
Примечание

Представьте, что у нас есть строка a = a1a2a3...a|a|, где |a| — это длина строки a, а ai — i-я буква строки.

Строку alal + 1al + 2...ar (1 ≤ l ≤ r ≤ |a|) будем называть подстрокой [l, r] строки a.

Подстрока [l, r] уникальная в a тогда и только тогда, когда нет пары l1, r1, такой, что l1 ≠ l и подстрока [l1, r1] равняется подстроке [l, r] в a.