LG4112

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=4007;

struct sam{
    int tot;
    int len[N];
    int trans[N][26];
    int fa[N];

    inline int NewNode(int mx,int *tr,int su){
        ++tot;
        len[tot]=mx;
        if(tr!=NULL)memcpy(trans[tot],tr,26<<2);
        fa[tot]=su;
        return tot;
    }

    inline int Extend(int u,int c){
        int t=NewNode(len[u]+1,NULL,0);
        for(;u&&!trans[u][c];u=fa[u])trans[u][c]=t;
        if(!u){
            fa[t]=1;
            return t;
        }
        int v=trans[u][c];
        if(len[v]==len[u]+1){
            fa[t]=v;
            return t;
        }
        int x=NewNode(len[u]+1,trans[v],fa[v]);
        fa[t]=fa[v]=x;
        for(;u&&trans[u][c]==v;u=fa[u])trans[u][c]=x;
        return t;
    }

    inline void build(char *s,int n){
        int lst=NewNode(0,NULL,0);
        for(int i=0;i<n;++i){
            lst=Extend(lst,s[i]-'a');
        }
    }
}samA,samB;

struct seq{
    int tot;
    int trans[N][26];
    inline void build(char *s,int n){
        tot=n+1;
        for(int i=n-1;~i;--i){
            memcpy(trans[i+1],trans[i+2],26<<2);
            trans[i+1][s[i]-'a']=i+2;
        }
    }
}seqA,seqB;

struct DAG{
    int tot;
    int *trans[N];

    DAG(sam &a){
        tot=a.tot;
        for(int i=1;i<=tot;++i)trans[i]=a.trans[i];
    }
    DAG(seq &a){
        tot=a.tot;
        for(int i=1;i<=tot;++i)trans[i]=a.trans[i];
    }
};

struct Data{
    int a,b,t;
};

bool vis[N][N];

inline int bfs(DAG A,DAG B){
    for(int i=1;i<=A.tot;++i){
        for(int j=1;j<=B.tot;++j){
            vis[i][j]=0;
        }
    }
    vis[1][1]=1;
    queue<Data>Q;
    Q.push(Data{1,1,0});
    while(!Q.empty()){
        Data t=Q.front();
        Q.pop();
        for(int i=0;i<26;++i){
            int x=A.trans[t.a][i];
            int y=B.trans[t.b][i];
            if(vis[x][y]||!x)continue;
            if(!y)return t.t+1;
            vis[x][y]=1;
            Q.push(Data{x,y,t.t+1});
        }
    }
    return -1;
}

char A[N];
char B[N];

int main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    scanf("%s%s",A,B);
    int lenA=strlen(A);
    int lenB=strlen(B);
    samA.build(A,lenA);
    seqA.build(A,lenA);
    samB.build(B,lenB);
    seqB.build(B,lenB);
    printf("%d\n",bfs(samA,samB));
    printf("%d\n",bfs(samA,seqB));
    printf("%d\n",bfs(seqA,samB));
    printf("%d\n",bfs(seqA,seqB));
}