Штаб-квартира полиции отслеживает сигналы на разных частотах. Недавно они записали две подозрительные строки, s1 и s2, на двух частотах. Полиция подозревает, что эти две строки принадлежат двум преступникам, планирующим сделать какое-то злое деяние.
Поэтому полиция пытается найти общую подстроку этих двух строк. Искомая подстрока должна быть уникальной в первой строке и во второй строке. Другими словами, она должна встречаться ровно один раз в первой строке и ровно один раз во второй строке. Среди всех таких строк, полицию интересует строка с минимальной длиной.
Вам даны две строки, s1 и s2, состоящие из строчных букв латинского алфавита. Чему равна длина минимальной по длине общей уникальной подстроки строк s1 и s2? Формальное определение подстроки и уникальности смотрите в примечании.
Выходные данные
Выведите длину наименьшей общей уникальной подстроки s1 и s2. Если общих уникальных подстрок у s1 и s2 нет, выведите -1.
Примечание
Представьте, что у нас есть строка 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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
apple
pepperoni
|
2
|
|
2
|
lover
driver
|
1
|
|
3
|
bidhan
roy
|
-1
|
|
4
|
testsetses
teeptes
|
3
|