Гасло міста

Обмеження: 2 сек., 256 МіБ

У честь 47-го дня року мерія Львова вирішила зробити дещо радикальний крок — змінити гасло міста. Нове гасло, на думку мерії, краще опише зв’язок міста з цим древнім та важливим святом.

Поточним гаслом міста є рядок \(s\), який складається з великих англійських букв. Мерія хоче, аби новим гаслом був рядок \(t\). Проте вони розуміють, що якщо просто в один день раптово змінять гасло міста, то наступить страшний хаос. Можливо, навіть маршрутки перестануть їздити.

Тож вони вирішили не ризикувати і втілювати зміни поступово: в один день вони можуть вибрати підпослідовність букв поточного гасла та видалити їх. Більше того, вони не можуть вибрати підпослідовність, яка буде містити більше двох однакових букв. Ніяким іншим чином модифікувати гасло не довзоляється.

Зауважте, що підпослідовніть може містити букви, які не йдуть підряд в рядку.

Допоможіть мерії знайти мінімальну кількість днів, за яку вони можуть перетворити гасло, або визначте, що це неможливо.

Вхідні дані

У першому рядку задано початкове гасло \(s\), а в другому — кінцеве \(t\).

Рядки містять лише великі букви англійського алфавіту.

Вихідні дані

У єдиному рядку виведіть мінімальну кількість днів, або -1, якщо досягнути цілі неможливо.

Обмеження

\(1 \le |s|, |t| \le 10^5\).

Приклади