Гасло міста

Limits: 2 sec., 256 MiB

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

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

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

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

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

Input

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

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

Output

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

Constraints

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

Samples