using namespace std;

class solver_this{
  public:
    solver_this(string _begin, string _target, vector<string> _words): begin(_begin), target(_target), words(_words){
        n = words.size();
    }
    bool checker(string now, string cmp){
        if (now != cmp){
            int same  = 0;
            for(int i = 0 ; i < now.length(); ++i)
                if ( now[i] == cmp[i])
                    same+=1;
            if (same == now.length()-1)
                return true;
        }
        return false;
    }
    
    void DFS(int iter, int answer, string now, vector<int> visited){
            for(int i = 0 ; i < words.size(); ++i){
                if (visited[i] == 0){
                    if (checker(now, words[i])){
                        string prev_now = now;
                        now = words[i];
                        visited[i] = 1;
                        cout << answer+1 << ": " << now << endl;
                        if (now == target){
                            cout << endl;
                            cases.push_back(answer+1);
                            return;
                        }
                        DFS(iter+1, answer+1, now, visited);
                        visited[i] = 0;
                        now = prev_now;
                    }
                }
            }
    }
    vector<int> cases;
    
  private:
    string begin, target;
    vector<string> words;
    int n;
    
};

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    
    solver_this solver(begin, target, words);
    
    int iter=0, mid_answer=0;
    string now =begin;
    vector<int> visited(words.size(),0);
        
    solver.DFS(iter, mid_answer, now, visited);
    
    if (solver.cases.size() ==0)
        answer = 0;
    else{
        sort(solver.cases.begin(), solver.cases.end());
        answer = *solver.cases.begin();
    }
    
    return answer;
}