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

using namespace std;

void search();
void clearQueue(queue<int>&);

std::unordered_map<int, int> pi; // Store predecessor
std::unordered_map<int, int> d; // Store depth
std::queue<int> Q;

static bool verb = false; // Verbose mode
static bool mmag = false; // doet operatie M mee
static int a = 0;
static int b = 0; // Beginpoint and endpoint

int main()
{
    string toks;
    bool c = true;  // continue??

    while (c)
    {
        cout << "-> ";
        getline(cin, toks);
        istringstream is(toks);
        char choice;
        int n;
        is >> choice >> n;
        switch (choice)
        {
        case 'a':
            a = n;
            break;
        case 'b':
            b = n;
            break;
        case 'v':
            verb = !verb;
            break;
        case 'm':
            mmag = !mmag;
            break;
        case 'x':
            c = false;
            break;
        case 's': //search
            // if B<A and M is not allowed, no solution exists
            if (a > b && !mmag)
            {
                cout << "Not possible.\n";
                break;
            }
            search();
            cout << b << " can be reached in " << d[b] << " steps.\n";
            break;
        case 'h':
            cout << "Gerard's BFS from A 2 B\n";
            cout << "a/b: Set a or b (now "<< a << " and " << b << ").\n";
            cout << "s  : Search.\n";
            cout << "v  : Toggle Verbose (now " << verb << ").\n";
            cout << "m  : Toggle use of M (now " << mmag << ").\n";
            cout << "x  : eXit.\n";
            break;
        }
    }
    return 0;
}

void search()
{
    // Throw out all old stuff from previous searches
    pi.clear();
    d.clear();
    clearQueue(Q);
    // Start search by enqueing a
    d.insert(std::make_pair(a, 0));
    Q.push(a);
    pi.insert(std::make_pair(a, a));
    if (a == b)
    {
        return;
    }

    // Process untill Q empty
    while (Q.size() > 0)
    {
        int u = Q.front(); //use element
        Q.pop();  //remove element
        // Successors of u are:  I(u) = u+1, maybe M(u) = u-1,  D(u) = 2u
        vector<int> Suc;
        Suc.push_back(u + 1);
        if (mmag)
        {
            Suc.push_back(u - 1);
        }
        Suc.push_back(2 * u);
        for (auto v : Suc)
        {
            if (pi.find(v) == pi.end()) //we didn find v
            {
                if (verb)
                {
                   cout << v << " is reached via " << u << " in " << (d[u] + 1) << " steps.\n";
                }
                Q.push(v);
                pi.insert(std::make_pair(v, u));
                d.insert(std::make_pair(v, d[u] + 1));

                // Stop when b is found
                if (v == b)
                {
                    return;
                }
            }
        }
    }

}

void clearQueue(queue<int>& q)
{
    queue<int> empty;
    swap(q,empty);
}