시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 1 | 1 | 1 | 100.000% |
Ildar is attending a boring online lesson. In order to do something, he transforms strings. Initially, he has a string $s$. Ildar wants to get a string $t$ from the string $s$ in minimum number of steps. In one step he can:
The minimum number of such steps needed to transform string $s$ into string $t$ is also known as edit distance between $s$ and $t$.
Ildar has $n$ favorite strings $w_i$. Consider sequence of strings that would occur during the transformation: $s = x_1$, $x_2$, \dots, $x_{m - 1}$, $x_m = t$. Ildar wants as many of $w_i$ as possible to appear in the set $\{x_1, x_2, \dots, x_m\}$. Help Ildar to find out what is the minimum number of steps needed to transform $s$ to $t$, and what is the maximum number of $w_i$ that can appear during this process, also print these strings.
The first line of input contains the string $s$.
The second line of input contains the string $t$.
The third line contains a single integer $n$ ($0 \le n \le 1\,000$). The following $n$ lines contain strings $w_i$.
All strings consist of lowercase English letters, are non-empty, their lengths don't exceed $10\,000$. The total length of all strings doesn't exceed $10\,000$. All strings are distinct, including $s \neq t$, $s \neq w_i$ and $t \neq w_i$.
Output two integers at the first line of output --- the minimum number of steps, needed to transform $s$ into $t$, and the maximum number of strings $w_i$ that can appear in the process of transformation.
After that, output strings $w_i$ that can appear during the transformation, in the same order they would appear. If there are multiple correct answers, you can output any of them.
cat dog 4 dot pot rat oat
3 1 dot
longlong double 3 doublon longleng dongle
6 2 longleng dongle
In the second example one of correct transformations is the following:
"longlong" $\rightarrow$ "longleng" $\rightarrow$ "dongleng" $\rightarrow$ "dongleg" $\rightarrow$ "dongle" $\rightarrow$ "donble" $\rightarrow$ "double"
Ildar's favorite strings are highlighted.