问题 J: 字串变换

内存限制:125 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:14 通过:8

题目描述

已知有两个字串A,B及一组字串变换的规则(至多6个规则):

A1 -> B1

A2 -> B2

规则的含义为:在 A中的子串A1可以变换为B1、A2可以变换为B2...


例如:A='abcd' B='xyz'

  变换规则为:

  'abc'->'xu' 'ud'->'y' 'y'->'yz'

  则此时,A可以经过一系列的变换变为B,其变换的过程为:

     'abcd'->'xud'->'xy'->'xyz'

  共进行了三次变换,使得A变换为B。


输入格式

每个测试文件只包含一组测试数据,每组输入的第一行输入两个字符串A和B。

第一行是两个给定的字符串 A 和 B。

接下来若干行,每行描述一组字串变换的规则。

所有字符串长度的上限为 20。

输入格式如下:

A B
A1 B1 
A2 B2   
... ...     



输出格式

对于每组输入数据,若在10步(包含10步)以内能将A变换为B,则输出最少的变换步数,否则输出"NO ANSWER!"。


输入样例 复制

abcd wyz
abc xu
ud y
y yz

输出样例 复制

3