#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

unordered_map<char, vector<char>> graph = {
    {'A', {'B', 'C', 'D'}},
    {'B', {'A', 'F', 'E'}},
    {'C', {'A', 'H', 'G'}},
    {'D', {'A', 'K', 'J', 'I'}},
    {'E', {'B', 'M', 'L'}},
    {'F', {'B', 'P', 'N'}},
    {'G', {'C', 'Q'}},
    {'H', {'C', 'R'}},
    {'I', {'D', 'S'}},
    {'J', {'D', 'T', 'U'}},
    {'K', {'D', 'V'}},
    {'L', {'E', 'W'}},
    {'M', {'E', 'Z', 'Y'}},
    {'N', {'F'}},
    {'P', {'F'}},
    {'Q', {'G'}},
    {'R', {'H'}},
    {'S', {'I'}},
    {'T', {'J'}},
    {'U', {'J'}},
    {'V', {'K'}},
    {'W', {'L'}},
    {'Y', {'M'}},
    {'Z', {'M'}}
};

int bfs(char start, char goal) {
    queue<vector<char>> q;
    unordered_map<char, bool> visited;
    q.push({ start });
    visited[start] = true;

    while (!q.empty()) {
        vector<char> path = q.front();
        q.pop();
        char node = path.back();

        if (node == goal) {
            cout << "Shortest path: ";
            for (char vertex : path) {
                cout << vertex << " -> ";
            }
            cout << "\b\b\b   \n"; 
            return path.size() - 1;
        }

        for (char adjacent : graph[node]) {
            if (!visited[adjacent]) {
                visited[adjacent] = true;
                vector<char> new_path = path;
                new_path.push_back(adjacent);
                q.push(new_path);
            }
        }
    }

    return -1; 
}

int main() {
    char start = 'Z';
    char goal = 'C';

    int operators = bfs(start, goal);
    if (operators != -1) {
        cout << "Number of operators on the path found by BFS: " << operators << endl;
    }
    else {
        cout << "Goal state not reachable from the initial state!" << endl;
    }

    return 0;
}