串的最少变换

普及⏱ 1000ms💾 256MB#P5041

题目描述

字符串变换游戏:给定不超过 $3$ 条替换规则 u -> v(都是小写字母串),每一步可以选一条规则,把当前串中任意一次出现的 u 替换为 v。问从串 A 变到串 B 最少需要几步?无法变到则输出 -1。(过程中串长始终不超过 $20$。)

输入格式

前三行依次为规则(若不足三条则以空行补足);第四行为串 A;第五行为串 B。

输出格式

一行一个整数:最少步数或 -1

数据范围

各串长 $\le 20$

样例输入 #1
a b

aaaa
bbbb
样例输出 #1
-1
样例输入 #2
ab ba


abba
baab
样例输出 #2
-1