P2138 Xiao Z's Relationship Distance

Xiao Z has studied dialectical materialism and learned that connections are universal. Looking at the strings on his scratch paper, he wants to explore the relationships between them. Xiao Z believes that for two strings $a,b$, if each can delete no more than half of its own length of characters to become equal, then $a,b$ are said to have a relationship with distance $1$. If there exists another string $c$ that has a distance of $1$ with $a$ and a distance of $n$ with $b$, then $a,b$ are said to have a relationship with distance $n + 1$. Now Xiao Z randomly selects two lowercase letter strings $a,b$ and wants to know the minimal relationship distance between them. Please help him.

The first line contains a string $a$. The second line contains a string $b$.

The first line contains an integer indicating the minimal relationship distance between $a,b$.

For $30\%$ of the testdata, $a,b$ are composed of the same letter. For $100\%$ of the testdata, $1 \leq |a|,|b| \leq 100$. Translated by ChatGPT 5