#include <stdio.h>

char	*name[] = {
	"",
	"01:北海道", 
	"02:青森県", "03:岩手県", "04:宮城県", "05:秋田県", "06:山形県", "07:福島県",
	"08:茨城県", "09:栃木県", "10:群馬県", "11:埼玉県", "12:千葉県", "13:東京都", "14:神奈川県",
	"15:新潟県", "16:富山県", "17:石川県", "18:福井県", "19:山梨県", "20:長野県",
	"21:岐阜県", "22:静岡県", "23:愛知県", "24:三重県",
	"25:滋賀県", "26:京都府", "27:大阪府", "28:兵庫県", "29:奈良県", "30:和歌山県",
	"31:鳥取県", "32:島根県", "33:岡山県", "34:広島県", "35:山口県",
	"36:徳島県", "37:香川県", "38:愛媛県", "39:高知県",
	"40:福岡県", "41:佐賀県", "42:長崎県", "43:熊本県", "44:大分県", "45:宮崎県", "46:鹿児島県", "47:沖縄県",
};

    int connect[][10] =
    {
		{ 1, 2}, // 1:北海道
		{ 2, 1, 3, 5}, // 2:青森県
		{ 3, 2, 4, 5}, // 3:岩手県
		{ 4, 3, 6, 7}, // 4:宮城県
		{ 5, 2, 3, 6}, // 5:秋田県
		{ 6, 3, 4, 5, 7,15}, // 6:山形県
		{ 7, 4, 6, 8, 9,10,15}, // 7:福島県
		{ 8, 6, 9,11,12}, // 8:茨城県
		{ 9, 7, 8,10}, // 9:栃木県
		{10, 7, 9,11,15,20}, // 10:群馬県
		{11, 8,10,12,13,20,19}, // 11:埼玉県
		{12, 8,11,13,14}, // 12:千葉県
		{13,11,12,14,19}, // 13:東京都
		{14,12,13,22,19}, // 14:神奈川県
		{15,16,20, 6, 7,10}, // 15:新潟県
		{16,15,17,20,21}, // 16:富山県
		{17,16,18,21}, // 17:石川県
		{18,16,17,21,26}, // 18:福井県
		{19,11,13,14,22,20,21}, // 19:山梨県
		{20,15,16,19,21,22,23}, // 20:長野県
		{21,16,17,18,20,22,23}, // 21:岐阜県
		{22,14,19,20,21,23}, // 22:静岡県
		{23,21,22,24,25,29}, // 23:愛知県
		{24,23,30,29}, // 24:三重県
		{25,26,29,18,21}, // 25:滋賀県
		{26,25,27,29}, // 26:京都府
		{27,26,28,29,30}, // 27:大阪府
		{28,27,26,33,31,36}, // 28:兵庫県
		{29,25,26,27,30,23,24}, // 29:奈良県
		{30,27,29,24}, // 30:和歌山県
		{31,32,33,34,28}, // 31:鳥取県
		{32,31,33,34,35}, // 32:島根県
		{33,31,32,34,37,28}, // 33:岡山県
		{34,31,32,33,35,38}, // 34:広島県
		{35,32,34,40}, // 35:山口県
		{36,37,39,28}, // 36:徳島県
		{37,36,38,39,33}, // 37:香川県
		{38,36,37,39,34}, // 38:愛媛県
		{39,36,37,38}, // 39:高知県
		{40,41,43,44,35}, // 40:福岡県
		{41,40,42,43}, // 41:佐賀県
		{42,41}, // 42:長崎県
		{43,40,41,44,45,46}, // 43:熊本県
		{44,40,43,45}, // 44:大分県
		{45,43,44,46}, // 45:宮崎県
		{46,43,45,47}, // 46:鹿児島県
		{47,46}, // 47:沖縄県
	{-1}
    };

int neigh[48][48];
void travel(int ken);
int main()
{
	int	i,j,k,ken,flag;

	/* 県ごとの隣接テーブルを作る */
	for(i=0;connect[i][0] != -1;i++) {
		ken = connect[i][0];
		for(j=1;j<10;j++) {
			if(connect[i][j]){
				neigh[ken][connect[i][j]] = 1;
				neigh[connect[i][j]][ken] = 1;
			}
		}
	}

	travel(47);			/* 沖縄から */
	return 0;
}

char	visited[48];
char	path[100];
int	pass = 0;

void travel(int ken)
{
	int	i,next,f;

	if(ken == 47 && pass > 0) {
		printf("==== result ====\n");
		printf("%s ", name[47]);
		for(i=0;i<pass;i++) {
			printf("-> %s", name[path[i]]);
		}
		exit(0);
	}

	/* 隣接県を全部試す */
	for(next=1; next<48; next++) {
		if(neigh[ken][next] == 0) continue;

		if(visited[next] >= 2) continue;
		visited[next]++;
		path[pass++] = next;
		travel(next);
		visited[next]--;
		pass -= 1;
	}
}