#include <iostream>
#include <string>
#include <deque>
#include <algorithm>

unsigned char table[352] =
{
    0x06, 0x09, 0x83, 0xC9, 0x86, 0xC5, 0xC5, 0x4D, 0x8F, 0xCD, 0x44, 0x85, 0x88, 0x81, 0x0C, 0x0F, 
    0xC3, 0x8B, 0x83, 0x8F, 0x0B, 0x4A, 0xCC, 0x83, 0x05, 0x4E, 0x85, 0x07, 0x8A, 0x0F, 0x8A, 0xC6, 
    0x8C, 0xC0, 0x0A, 0x86, 0x06, 0x06, 0x8C, 0x48, 0x8A, 0x86, 0x4C, 0x44, 0x4A, 0x86, 0xCC, 0x8D, 
    0x4A, 0x46, 0xC6, 0x06, 0x86, 0x8C, 0x0B, 0x8A, 0xCC, 0x09, 0xC7, 0x89, 0x00, 0x0B, 0x0E, 0x4D, 
    0x05, 0x83, 0x0B, 0xC3, 0x86, 0x8D, 0x49, 0xC9, 0x42, 0x89, 0x8C, 0xC9, 0x41, 0x49, 0xCF, 0x00, 
    0x44, 0x88, 0x89, 0x0A, 0x0B, 0x85, 0x06, 0xC1, 0x0B, 0x06, 0x0F, 0xDF, 0x8F, 0x86, 0x06, 0x8C, 
    0x82, 0x07, 0x01, 0x8C, 0x83, 0xC6, 0x45, 0x0C, 0xC9, 0x48, 0x61, 0x08, 0xCA, 0x4C, 0xCF, 0x89, 
    0x04, 0x49, 0x4A, 0x06, 0x8D, 0x89, 0x03, 0x0B, 0x87, 0x8D, 0xC1, 0xC6, 0x43, 0x0C, 0xCE, 0x8C, 
    0x0E, 0xC2, 0xCE, 0x4B, 0xC1, 0x89, 0x0C, 0x87, 0x45, 0x8B, 0xCD, 0xC8, 0x49, 0x4E, 0xC3, 0x0C, 
    0x0A, 0xCA, 0xC9, 0x4A, 0xC1, 0x46, 0x43, 0x46, 0x04, 0xCE, 0x03, 0x86, 0xC6, 0xC6, 0x86, 0x46, 
    0xC6, 0x46, 0x87, 0x06, 0xC6, 0x46, 0x07, 0x4D, 0xC9, 0x21, 0xC5, 0x4B, 0x09, 0xC8, 0x02, 0x89, 
    0x85, 0x41, 0x86, 0x46, 0x88, 0x89, 0x4A, 0x09, 0x07, 0xCF, 0x42, 0x8A, 0x4B, 0x0E, 0x8E, 0x0D, 
    0xC4, 0x0A, 0x44, 0x0F, 0x89, 0x8F, 0x06, 0x8E, 0x4A, 0x45, 0x45, 0xC6, 0x01, 0x85, 0x00, 0x0A, 
    0xC6, 0x4C, 0x4E, 0x08, 0x42, 0x48, 0x8F, 0x46, 0x03, 0xCA, 0x4C, 0x8C, 0x86, 0x0D, 0x8A, 0x0C, 
    0xCA, 0x43, 0x46, 0x4C, 0xC8, 0x89, 0x04, 0x0E, 0x4B, 0x85, 0xC9, 0xCB, 0x89, 0x05, 0x49, 0x04, 
    0x8B, 0x46, 0x0D, 0x08, 0x82, 0x06, 0x4F, 0x87, 0x86, 0x0C, 0xC4, 0x43, 0x05, 0x46, 0xCC, 0xC7, 
    0x49, 0x08, 0x43, 0xCC, 0x82, 0x4D, 0x0A, 0x46, 0x0E, 0x4D, 0x49, 0xCB, 0x86, 0x0D, 0x87, 0x49, 
    0x8B, 0xCA, 0x0C, 0xC9, 0x8B, 0x4B, 0x49, 0x83, 0x48, 0xC3, 0x8D, 0xCF, 0x4F, 0x09, 0xC1, 0x8F, 
    0x89, 0x85, 0x88, 0xA1, 0x43, 0x03, 0x85, 0x41, 0x01, 0x01, 0x41, 0x85, 0x83, 0x86, 0x06, 0x46, 
    0x87, 0x84, 0x86, 0x43, 0x46, 0xC6, 0xC6, 0x46, 0x46, 0x46, 0x85, 0xC7, 0x62, 0xC5, 0xC3, 0x47, 
    0x88, 0x81, 0x04, 0xC1, 0x82, 0x4C, 0x08, 0x44, 0xC0, 0xC7, 0x47, 0xCA, 0x88, 0x45, 0x0B, 0x0A, 
    0x00, 0x07, 0x45, 0x4A, 0x4F, 0x47, 0xC6, 0x0E, 0xC1, 0x09, 0x0C, 0x0C, 0x00, 0x00, 0x00, 0x00, 
} ;

bool matrix[sizeof(table)][sizeof(table)] = { { false } };

void fillAdjacencyMatrix()
{
	for (unsigned int i=0;i<sizeof(table);i++)
	{
		if (i >= 0x1D && (table[i - 0x1D] >> 3) & 1)
		{
			matrix[i][i - 0x1D] = true;
		}
		
		if (i < sizeof(table) - 1 && (table[i + 0x01] >> 2) & 1)
		{
			matrix[i][i + 1] = true;
		}
		
		if (i > 0 && (table[i - 0x01] >> 1) & 1)
		{
			matrix[i][i - 1] = true;
		}
		
		if (i < sizeof(table) - 0x1D && (table[i + 0x1D] & 1))
		{
			matrix[i][i + 0x1D] = true;
		}
	}
}

std::deque<unsigned int> shortestPathInternal(unsigned int start, unsigned int end, std::deque<unsigned int> visited)
{
	if (start == end)
	{
		std::deque<unsigned int> path;
		path.push_back(end);
		return path;
	}
	
	visited.push_back(start);
		
	std::deque<unsigned int> minPath;

	for (unsigned int i=0;i<sizeof(table);i++)
	{
		if (matrix[start][i] && std::find(visited.begin(), visited.end(), i) == visited.end())
		{
			try
			{
				std::deque<unsigned int> nmp = shortestPathInternal(i, end, visited);
				
				if (nmp.size() && nmp[nmp.size() - 1] == end && (minPath.size() == 0 || nmp.size() < minPath.size()))
				{
					minPath = nmp;
				}
			}
			catch(...)
			{
				// Ignore
			}
		}
	}
	
	if (minPath.size() == 0)
	{
		throw "No path found";
	}
	
	minPath.push_front(start);
	
	return minPath;
}

std::deque<unsigned int> shortestPath(unsigned int start, unsigned int end)
{
	std::deque<unsigned int> visited;
	return shortestPathInternal(start, end, visited);
}

std::string pathToPassword(const std::deque<unsigned int>& p)
{
	std::string pwd;
	
	for (unsigned int i=1;i<p.size();i++)
	{
		if (p[i] == p[i-1] + 0x1D) pwd += "2";
		else if (p[i] == p[i-1] - 0x01) pwd += "4";
		else if (p[i] == p[i-1] + 0x01) pwd += "6";
		else if (p[i] == p[i-1] - 0x1D) pwd += "8";
		else throw "Invalid path";
	}
	
	return pwd;
}

int main()
{
	fillAdjacencyMatrix();
	
	try
	{
		std::deque<unsigned int> sp = shortestPath(0x5B, 0x123);
		
		std::string pwd = pathToPassword(sp);
		
		std::cout << "The password is " << pwd << std::endl;
	}
	catch(const char* msg)
	{
		std::cout << msg << std::endl;
	}
}