from collections import deque

start,target = input().split()

a = []
b = []

n = 0
while True:
    try:
        line = input().split()
        a.append(line[0])
        b.append(line[1])
        n += 1
    except:
        break


"""
扩展函数，扩展q队列的一整层

参数：
q:扩展的队列
如果q对应的是起点拓展的队列，那么da对应到起点的距离，db对应到终点的距离
如果q对应的是终点拓展的队列，那么da对应到终点的距离，db对应到起点的距离
a[]和b[]代表规则从a数组->b数组

返回值：满足条件的最小步数
"""
def extend(q, da, db, a, b):
    size = len(q)
    # 扩展一整层
    # extend函数必须扩展一整层的所有孩子，不能只能只扩展一个状态结点的所有孩子
    while size > 0:
        size -= 1
        cur = q.popleft()
        for i in range(n): # 枚举所有字串变换的规则
            ca, cb = a[i], b[i] # ca可以应用规则转变成cb
            for j in range(len(cur)): 
                if cur[j : j + len(ca)] == ca:# 如果cur字符串中有能与规则相匹配的字符串段
                    ne = cur[: j] + cb + cur[j + len(ca) :] # 应用该规则扩展到下一个状态
                    if ne in da: # 如果该状态已经扩展到了，则continue
                        continue

                    # 如果ne状态落到db里面去，两个方向会师，返回最小步数
                    if ne in db: 
                        return da[cur] + 1 + db[ne] 
                    da[ne] = da[cur] + 1
                    q.append(ne)
    return 11 # 如果扩展了q队列的一整层两个方向依然没有会师，则返回11，代表没有成功


def bfs():
    qa, qb = deque(), deque()
    da, db = {}, {}
    da[start], db[target] = 0, 0
    qa.append(start)
    qb.append(target)
    step = 0 # 记录步数

    # 只有当qa和qb同时存在点的时候说明才有可能相遇
    # 否则只要有一个队列为空，说明该方向已经搜到尽头了都没搜到另一个队列中存在的状态，所以起点和终点不连通    
    while qa and qb:
        # 从节点少的队列开始拓展时间复杂度较小
        # 因为节点少的队列，它拓展出来的分支也少，从而能避免枚举那些无意义的字符串
        if len(qa) <= len(qb):
            t = extend(qa, da, db, a, b)
        else:
            t = extend(qb, db, da, b, a)
        step += 1
        if t <= 10:
            return t
        if step == 10: # 如果变换步数已经为10了，还没能变换成功，则输出 NO ANSWER!
            return -1

    # 只要有一个队列为空，说明该方向已经搜到尽头了都没搜到另一个队列中存在的状态，所以起点和终点不连通
    return -1

if start == target: # 特判起始状态和目标状态相等的情况
    print(0)
    exit(0)

t = bfs()
if t == -1:
    print('NO ANSWER!')
else:
    print(t)