//程序算法：双向搜索
#include <bits/stdc++.h>
using namespace std;
const int N=7;

string from[N],to[N];
string a,b;
int n=1;

queue<string> q1,q2;
unordered_map<string,int> M1,M2;

void extend(queue<string>& q,unordered_map<string,int>& M1,unordered_map<string,int>& M2)
{
    if(q.empty())return; //防止因队列为空取front导致RE

    string u=q.front(),str=u;
    q.pop();

    for(int i=1;i<=n;i++)
    {
        int pos=0;
        while(true)
        {
            pos=str.find(from[i],pos);
            if(pos==string::npos)break;
            
            string v=str;
            v.replace(pos,from[i].size(),to[i]);

            if(M1.count(v))
            {
                pos++; //这里必须pos++，否则continue后无法pos++死循环，Line 36同理
                continue;
            }
            else if(M1[u]+1>10)
            {
                pos++;
                continue;
            }
            else M1[v]=M1[u]+1;

            if(M2.count(v))
            {
                cout<<M1[v]+M2[v]<<endl;
                exit(0);
            }

            q.push(v);
            pos++;
        }
    }
}

void bfs()
{
    M1[a]=0,M2[b]=0;
    q1.push(a),q2.push(b);

    while(true)
    {
        extend(q1,M1,M2);
        extend(q2,M2,M1);
    }
}

void fast_read()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
    
    fast_read();
    
    cin>>a>>b;
    while(cin>>from[n]>>to[n])n++;
    n--;
    
    bfs();
    return 0;
}