#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>

struct Info {
	std::string sfen;
};
struct SearchInfo {
	SearchInfo(std::string& S, std::size_t I) :sfen(S), Index(I) {}
	std::string sfen="0";
	std::size_t Index=0;
};
//typedef std::map<std::string, std::vector<Info>> Tree;
typedef std::vector<std::string> GraphData;
typedef std::map<std::string, GraphData> Graph;
typedef std::vector<SearchInfo> SI;

Graph MakeTree() {
	Graph R{ {"0",{"1","3","5"}},{"1",{"0","4","6"}}, {"2",{"4","5","6"}},{"3",{"0","5","7"}}, {"4",{"1","3","7"}},{"5",{"2","0","3"}}, {"6",{"1","2","7"}},{"7",{"6","3","8"}},{"8",{"7"}} };
	return R;
}
SI Search(Graph& G, std::string Start, std::string End,std::size_t DepthLim) {

	if (DepthLim == 1) return SI();

	std::string Now = Start;
	std::size_t Si = 1;
	SI S{ {Start,0}, };
	while (Now != End) {
		if (G[Now].size() == S.back().Index) {
			S.pop_back();
			if (S.size() == 0) return SI();
			Now = S.back().sfen;
			continue;
		}
		Now = G[Now][S.back().Index++];
		if (S.end() != std::find_if(S.begin(), S.end(), [&](SearchInfo& o) {return o.sfen == Now; })) continue;
		S.push_back({Now,0});
		if (S.size() > DepthLim) {
			S.pop_back();
			if (S.size() == 0) return SI();

		}
	}

	SI si = Search(G, Start, End, S.size() - 1);
	if (si.size() != 0&& si.size()<S.size()) S = si;

	return S;
}

int main() {
	Graph G = MakeTree();
	SI S;
	S = Search(G, "0", "8",99);

	for (auto&o : S) {
		std::cout << o.sfen << std::endl;
	}

	return 0;
}