#include <string>
#include <vector>
using namespace std;
int chk[50];
int answer = -1;

void dfs(vector<string> &words, string begin, int idx,int cnt){
    string str=words[idx];
    int c=0;
    for(int i=0;i<words[0].size();i++){
        if(str[i]==begin[i]){
                c++;
         }
    }
    if(c==words[0].size()-1){
        if(answer==-1 || answer>cnt){
            answer=cnt;
        }
        return;
    }
    
    for(int i=0;i<words.size();i++){
        if(chk[i]==0){
            int c=0;
            for(int j=0;j<words[0].size();j++){
                if(str[j]==words[i][j]){
                    c++;
                }
            }
            if(c==words[0].size()-1){
                chk[i]=1;
                dfs(words,begin,i,cnt+1);
                chk[i]=0;
            }
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    //words중 target부터시작해서 (없으면 0리턴)
    //1글자 빼고 같은것들로 dfs() 수행한다.
    int startIdx=-1;
    for(int i=0;i<words.size();i++){
        if(target==words[i]){
            startIdx=i;
            break;
        }    
    }
    if(startIdx==-1){
        return 0;
    }
    chk[startIdx]=1;
    dfs(words,begin,startIdx,1);
    return answer;
}