String Relationship Distance

Let two strings \(a\) and \(b\) (consisting of lowercase letters) be given. We say that \(a\) and \(b\) have a distance-1 relationship if it is possible to delete no more than half of the characters (i.e. at most \(\lfloor \frac{|a|}{2}\rfloor\) for \(a\) and \(\lfloor \frac{|b|}{2}\rfloor\) for \(b\)) from each string so that the resulting strings become identical.

Formally, for a string \(x\) of length \(|x|\) the deletion is allowed if the remaining subsequence has length at least \(\lceil \frac{|x|}{2} \rceil\). Thus, \(a\) and \(b\) have a distance-1 relationship if there exists a string \(s\) such that \(s\) is a subsequence of both \(a\) and \(b\) and \[ |s| \ge \max\Big(\lceil \frac{|a|}{2} \rceil,\,\lceil \frac{|b|}{2} \rceil\Big). \]

Furthermore, we define the relationship recursively: if there exists a string \(c\) such that \(a\) and \(c\) have a distance-1 relationship, and \(c\) and \(b\) have a distance-n relationship, then we say that \(a\) and \(b\) have a distance-\(n+1\) relationship.

Given two strings \(a\) and \(b\), determine the minimum relationship distance between them. If there is no sequence of strings connecting \(a\) and \(b\) under the above rules, output -1.

Note: It can be proved that if \(a\) and \(b\) share no common character at all, then no sequence of intermediate strings can connect them, so the answer in that case is -1.

Observation: A direct distance-1 relationship exists if the length of the longest common subsequence (LCS) of \(a\) and \(b\) is at least \(\max\big(\lceil \frac{|a|}{2} \rceil,\,\lceil \frac{|b|}{2} \rceil\big)\). In our intended solution we check for this first. If this condition fails and \(a\) and \(b\) have at least one common character, it turns out that they can be connected with a chain of two steps (i.e. distance 2). Otherwise, if they share no common character, the answer is -1.

Your task is to implement this logic.

inputFormat

The input consists of two lines. The first line contains the string \(a\) and the second line contains the string \(b\). Both strings consist only of lowercase English letters.

outputFormat

Output a single integer: the minimum relationship distance between \(a\) and \(b\), or -1 if there is no valid relationship.

sample

ab
bb

1