#include <bits/stdc++.h>
using namespace std;

bool isTwoDiff(const string &a, const string &b) {
    if (a.size() != b.size()) return false;
    int diff = 0;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) diff++;
        if (diff > 2) return false;
    }
    return diff == 2;
}

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> dict(wordList.begin(), wordList.end());
    if (!dict.count(endWord)) return 0;

    queue<pair<string,int>> q;
    q.push({beginWord, 1});

    unordered_set<string> visited;
    visited.insert(beginWord);

    while (!q.empty()) {
        auto [word, steps] = q.front(); q.pop();
        if (word == endWord) return steps;

        for (auto it = dict.begin(); it != dict.end(); ) {
            string next = *it;
            if (!visited.count(next) && isTwoDiff(word, next)) {
                q.push({next, steps + 1});
                visited.insert(next);
                it = dict.erase(it); // remove from dict for efficiency
            } else {
                ++it;
            }
        }
    }
    return 0;
}

int main() {
    string beginWord = "hit", endWord = "cog";
    vector<string> wordList = {"hot","dot","dog","lot","log","cog","hit","hog","cot"};
    cout << ladderLength(beginWord, endWord, wordList) << endl;
    return 0;
}