Description

You are given two strings $A, B$ and a set of string transformation rules (at most $6$ rules), of the form:

• $A_1 \to B_1$.
• $A_2 \to B_2$.

The meaning of the rules is: in $A$, a substring $A_1$ can be transformed into $B_1$, $A_2$ can be transformed into $B_2 \cdots$.

For example: $A=\texttt{abcd}$, $B=\texttt{xyz}$,

with the transformation rules:

• $\texttt{abc}\rightarrow\texttt{xu}$, $\texttt{ud}\rightarrow\texttt{y}$, $\texttt{y}\rightarrow\texttt{yz}$.

Then $A$ can be transformed into $B$ through a sequence of transformations:

• $\texttt{abcd}\rightarrow\texttt{xud}\rightarrow\texttt{xy}\rightarrow\texttt{xyz}$.

A total of $3$ transformations are performed to transform $A$ into $B$.

Input Format

The first line contains two strings $A, B$.

Each of the following lines contains two strings $A_i, B_i$, representing one transformation rule.

Output Format

If $A$ can be transformed into $B$ within $10$ steps (inclusive), output the minimum number of steps; otherwise, output NO ANSWER!.

abcd xyz
abc xu
ud y
y yz

3

Hint

For $100\%$ of the testdata, the maximum length of all strings is $20$.

Source: NOIP 2002 Senior, Problem 2.

Translated by ChatGPT 5