Когда Махмуд и Ехаб готовились к Международной олимпиаде по информатике, они встретились с задачей о наибольшей общей подпоследовательности. Они ее решили, а после этого Ехаб задал Махмуду другую задачу.
Дано две строки a и b, найдите длину их наибольшей не общей подпоследовательности, то есть такой строки, которая является подпоследовательностью одной строки и не является подпоследовательностью другой.
Подпоследовательность некоторой строки это последовательность букв, которая встречается в том же порядке в строке, не обязательно подряд. Например, строки «ac», «bc», «abc» и «a» являются подпоследовательностями строки «abc», а строки «abbc» и «acb» — нет. Пустая строка является подпоследовательностью любой строки, любая строка является подпоследовательностью ее самой.
Выходные данные
Если наибольшей не общей подпоследовательности не существует, выведите «-1».
Иначе выведите длину наибольшей не общей подпоследовательности строк a и b.