문자열 거리

문자열 O에서 문자열 N까지의 문자열 거리는, O를 N과 같게 만들기 위해 수행해야 하는 문자열 삽입 횟수의 최솟값이다. 한 번의 삽입에서는 O의 맨 앞, 맨 뒤, 또는 두 문자 사이 원하는 위치에 임의의 문자열을 끼워 넣을 수 있다.

두 문자열 O와 N이 주어질 때, O에서 N까지의 문자열 거리를 구하라.

첫째 줄에 문자열 O, 둘째 줄에 문자열 N이 주어진다. 각 문자열의 길이는 1,000 이하이다. 문자열은 ASCII 코드 값이 32 이상 126 이하인 문자로만 이루어진다. 줄 전체가 문자열이므로 공백도 문자열에 포함된다.

첫째 줄에 문자열 O와 문자열 N의 문자열 거리를 출력한다. O를 N으로 만들 수 없다면 -1을 출력한다.