Turning A into B

Given two equal-length uppercase strings A and B, find the minimum number of moves that bring a chosen character to the front of A so that A becomes B, or -1 if impossible.

Medium5StringGreedyTwo pointersHash mapInterviewNo attempts yetTime limit2sMemory limit512 MB

Description

Examples5

Problem

You are given two strings A and B. One operation picks a single character of A and moves it to the very front of the string.

Write a program that computes the minimum number of operations needed to turn A into B.

Input

The first line contains A and the second line contains B. The two strings have the same length, which is at most 50, and both consist of uppercase letters only.

Output

Print the minimum number of operations that turns A into B. If A cannot be turned into B, print -1.