#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},
        {2, 3, 5},
        {3, 4, 5, 6},
        {4, 5, 6, 7},
        {5, 6},
        {6, 7, 15},
        {7, 8, 9, 10, 15},
        {8, 9, 11, 12},
        {9, 10, 11, 12, 13},
        {10, 11, 19, 20},
        {11, 12, 13, 19, 20},
        {12, 13},
        {13, 14, 19},
        {14, 19},
        {15, 16, 20},
        {16, 17, 20, 21},
        {17, 18, 21},
        {18, 21,25,26},
        {19, 20,22},
        {20, 22,23},
        {21, 23,24,25},
        {22, 23},
        {23, 24},
        {24, 25,26,29},
        {25, 26,27,29},
        {26, 27,28,29},
        {27, 28,29,30},
        {28, 31,33},
        {29, 30},
        {31, 32,33,34},
        {32, 33,34,35},
        {33, 34,37},
        {34, 35,38},
        {35, 40},
        {36, 37,38,39},
        {37, 38,39},
        {38, 39},
        {40, 41,43,44},
        {41, 42,43},
        {43, 44,45,46},
        {44, 43,45},
        {45, 46},
        {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;
	}
}