IMPA/p12101/p12101.cpp

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <utility>
#include <vector>
#include <iomanip>
#include <sstream>
#include <climits>
#include <queue>

using namespace std;

typedef unsigned int nat;

struct Edge;
struct Node;

struct Node
{
    Node(nat id) : id{id} {}

    nat id;
    vector<Edge*> edges;
};

struct Edge
{
    Edge(Node *a, Node *b) : a{a}, b{b}
    {
        a->edges.push_back(this);
        b->edges.push_back(this);
    }

    Node *other(Node *curr) const
    {
        if(curr == a)
            return b;

        return a;
    }

    Node *a;
    Node *b;
};

vector<bool> prime_sieve(nat upper_limit)
{
    ++upper_limit;
    vector<bool> primes(upper_limit, true);
    primes[0] = false;
    primes[1] = false;
    for(nat i = 2; i < upper_limit; ++i)
    {
        if(!primes[i])
            continue;

        for(nat j = 2*i; j < upper_limit; j += i)
        {
            primes[j] = false;
        }
    }

    return primes;
}



bool neighbours(Node *a, Node *b)
{
    nat a_val = a->id, b_val = b->id;

    nat diffs = 0;

    for(nat i = 0; i < 4; ++i)
    {
        if((a_val% 10) != (b_val% 10))
        {
            ++diffs;
        }
        a_val /= 10;
        b_val /= 10;
    }

    return (diffs == 1);
}

Node *get_by_id(vector<Node*> const &graph, nat id)
{
    for(auto n : graph)
    {
        if(n->id == id)
            return n;
    }
    return nullptr;
}

vector<Node*> make_graph(const vector<bool> &primes)
{
    vector<Node*> graph(primes.size());

    for(nat i = 0; i < primes.size(); ++i)
    {
        graph[i] = new Node(i);
    }

    for(nat i = 1001; i < primes.size(); i += 2)
    {
        if(!primes[i])
            continue;

        for(nat j = i+2; j < primes.size(); j += 2)
        {
            if(primes[j] && neighbours(graph[i], graph[j]))
            {
                new Edge(graph[i], graph[j]);
            }
        }
    }

    return graph;
}

nat BFS_len(Node *source, Node *target)
{
    queue<pair<Node*, nat>> q;

    q.push(make_pair(source, 0));

    vector<bool> visited(10001, false);
    visited[source->id] = true;

    while(!q.empty())
    {
        Node *curr = q.front().first;
        nat depth = q.front().second;
        q.pop();

        if(curr == target)
        {
            return depth;
        }

        for(Edge *e : curr->edges)
        {
            Node *other = e->other(curr);

            if(!visited[other->id])
            {
                q.push(make_pair(other, depth+1));
                visited[other->id] = true;
            }
        }
    }

    return (nat)-1;
}

int main()
{
    vector<bool> primes = prime_sieve(10000);
    vector<Node*> graph = make_graph(primes);

    nat num_tests, source, target;

    /*
    while(cin >> source)
    {
        for(auto e : graph[source]->edges)
        {
            cout << e->other(graph[source])->id << endl;
        }
    }

    return 0;
/*/

    /*
    while(cin >> source)
    {
        cout << primes[source] << endl;
    }

    return 0;
//*/

    cin >> num_tests;


    for(nat i = 0; i < num_tests; ++i)
    {
        cin >> source >> target;

        nat len = BFS_len(graph[source], graph[target]);

        if(len == (nat)-1)
        {
            cout << "Impossible" << endl;
        }
        else
        {
            cout << len << endl;
        }

    }

    return 0;
}