Description

At Xiaoming’s school, there are several girls. Xiaoming thinks each girl’s traits can be abstracted into a $6$-digit string that contains, without repetition, the digits $1\sim6$.

In Xiaoming’s mind, there is an ideal girl whose trait string is $A$. If string $Y$ is obtained from string $X$ by swapping two consecutive digits, then we say that trait strings $X$ and $Y$ are similar. First, Xiaoming finds his deskmate, whose trait string is $S$. Each time, Xiaoming looks for a girl whose trait string is similar to the current string, until he finds one suitable for him (that is, a girl whose trait string is identical to $A$ or similar to $A$). Define each girl’s suitability degree as the minimum number of girls he needs to look for to reach this person (including his deskmate and this person herself). Clearly, the smaller the suitability degree, the more suitable the girl is for Xiaoming.

However, Xiaoming feels that fate will not let him find her easily, so he believes that the second smallest suitability degree is actually his best match (that is, Xiaohong). Please write a program to compute Xiaohong’s suitability degree for Xiaoming.

Input Format

The $1$st line: a trait string $A$.

The $2$nd line: a trait string $S$.

Output Format

One line with a non-negative integer representing Xiaohong’s suitability degree.

123654
123456

3

Hint

Sample explanation:

The two shortest “suitable strings” are $\tt 454$ and $\tt 545$, so the answer is $3$.

For all testdata, it is guaranteed that strings $A$ and $S$ are valid, and that a solution exists.

Translated by ChatGPT 5