#include<bits/stdc++.h>
using namespace std;
template <typename T>
class Graph{
	map<T,list<T>> l;
public:
	void addEdge(int x, int y){
		l[x].push_back(y);
		l[y].push_back(x);
	}
	void bfs(T src, T destination){
		map<T,T> parent;
		map<T,int> distance;
		queue<T> q;
		//all other nodes will have INT_MAX value
		for(auto node_pair:l){
			T node= node_pair.first;
			distance[node]=INT_MAX;
		}
		q.push(src);
		distance[src]=0;
		parent[src]=src;
		while(!q.empty()){
			T node=q.front();
			q.pop();
			for(int neighbour:l[node]){
				if(distance[neighbour]==INT_MAX){
					q.push(neighbour);
					//mark that neighbour as visited
					distance[neighbour]=distance[node]+1;
					parent[neighbour]=node;
				}
			}
		}
		//print distance to every node
		for(auto node_pair:l){
			T node=node_pair.first;
			int d=distance[node];
			cout<<"Node "<<node<<" distance from src is "<<d<<endl;
		}
	
	//print distance to every node
	for(auto node_pair:l){
		cout<<node_pair.first<<" and distance "<<distance[node_pair.first]<<endl;
	}
	T temp=destination;
	while(temp!=src){
		cout<<temp<<"<--";
		temp=parent[temp];
	}
		cout<<src<<endl;

	cout<< distance[destination];
    }
};
int main()
{
	int board[50]={0};
	//snakes // ladders
	board[2]=13;
	board[5]=2;
	board[9]=18;
	board[18]=11;
	board[17]=-13;
	board[20]=-14;
	board[24]=-8;
	board[25]=10;
	board[32]=-2;
	board[34]=-22;
	//Add edges to graph
	Graph<int> g;
	for(int i=0;i<=37;i++){
		for(int dice=1;dice<=6;dice++){
			int j=i+dice;
			j+=board[j];
			if(j<=36){
				g.addEdge(i,j);
			}
		}
	}
	g.addEdge(36,36);
    g.bfs(0,36);
   
   return 0;
}