P2133 A Match Made in Heaven

Life is an A\*; you are my first goal state. — Xiaoming.

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.

The $1$st line: a trait string $A$. The $2$nd line: a trait string $S$.

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

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