program dm6;

const n=9;

var G: array[1..n,1..n] of integer;
    presist:array[1..n] of integer;
    short:array[1..n] of integer;
    i,j,a1,a2,a3,a4,a5,a6,a7,a8,a9,number,number2:integer;

begin
	for i:=1 to n do
	for j:=1 to n do
		G[i,j]:=0;
	for i:=1 to n do
		presist[i]:=0;
	G[1,1]:=1; G[1,2]:=1; G[1,3]:=1; G[1,4]:=1; G[1,7]:=1;
	G[2,1]:=1; G[2,2]:=1; G[2,3]:=1; G[2,5]:=1; G[2,8]:=1;
	G[3,1]:=1; G[3,2]:=1; G[3,3]:=1; G[3,6]:=1; G[3,8]:=1;
	G[4,1]:=1; G[4,4]:=1; G[4,5]:=1; G[4,7]:=1;
	G[5,2]:=1; G[5,4]:=1; G[5,5]:=1; G[5,7]:=1; G[5,8]:=1;
	G[6,3]:=1; G[6,6]:=1; G[6,9]:=1;
	G[7,1]:=1; G[7,4]:=1; G[7,5]:=1; G[7,7]:=1; G[7,9]:=1;
	G[8,2]:=1; G[8,3]:=1; G[8,5]:=1; G[8,8]:=1; G[8,9]:=1;
	G[9,6]:=1; G[9,7]:=1; G[9,8]:=1; G[9,9]:=1;
	writeln('matrix is');
	for j:=1 to n do
	begin
	for i:=1 to n do
		write(G[i,j],' ');
	writeln;
	end;
	number:=999;
	number2:=0;
	for a1:=1 to n do
	begin
	presist[a1]:=1;
	number2:=number2+1;
	for a2:=1 to n do
	begin
	number2:=number2+1;
	presist[a2]:=1;
	if G[a1,a2]=1 then
		for a3:=1 to n do
		begin
		number2:=number2+1;
		presist[a3]:=1;
		if G[a2,a3]=1 then
		for a4:=1 to n do
		begin
		number2:=number2+1;
		presist[a4]:=1;
		if G[a3,a4]=1 then
			for a5:=1 to n do
			begin
			number2:=number2+1;
			presist[a5]:=1;
			if G[a4,a5]=1 then
			for a6:=1 to n do
			begin
			number2:=number2+1;
			presist[a6]:=1;
			if G[a5,a6]=1 then
				for a7:=1 to n do
				begin
				number2:=number2+1;
				presist[a7]:=1;
				if G[a6,a7]=1 then
				for a8:=1 to n do
				begin
				number2:=number2+1;
				presist[a8]:=1;
				if G[a7,a8]=1 then
					for a9:=1 to n do
					if G[a8,a9]=1 then
					begin
					number2:=number2+1;
					presist[a9]:=1;
					if number2<number then
					if presist[1]=1 then
					if presist[2]=1 then
					if presist[3]=1 then
					if presist[4]=1 then
					if presist[5]=1 then
					if presist[6]=1 then
					if presist[7]=1 then
					if presist[8]=1 then
					if presist[9]=1 then
					begin
					short[1]:=a1; short[2]:=a2; short[3]:=a3; short[4]:=a4; short[5]:=a5;
					short[6]:=a6; short[7]:=a7; short[8]:=a8; short[9]:=a9;
					end;
					number2:=number2-1;	
					if a9<>a8 then
					if a9<>a7 then
					if a9<>a6 then
					if a9<>a5 then
					if a9<>a4 then
					if a9<>a3 then
					if a9<>a2 then
					if a9<>a1 then
					presist[a9]:=0;
					end;
				number2:=number2-1;
				if a8<>a7 then
				if a8<>a6 then
				if a8<>a5 then
				if a8<>a4 then
				if a8<>a3 then
				if a8<>a2 then
				if a8<>a1 then
				presist[a8]:=0;	
				end;
				number2:=number2-1;
				if a7<>a6 then	
				if a7<>a5 then	
				if a7<>a4 then	
				if a7<>a3 then	
				if a7<>a2 then	
				if a7<>a1 then	
				presist[a7]:=0;	
				end;
			number2:=number2-1;
			if a6<>a5 then
			if a6<>a4 then
			if a6<>a3 then
			if a6<>a2 then
			if a6<>a1 then
			presist[a6]:=0;	
			end;
			number2:=number2-1;
			if a5<>a4 then
			if a5<>a3 then
			if a5<>a2 then
			if a5<>a1 then
			presist[a5]:=0;		
			end;
		number2:=number2-1;
		if a4<>a3 then
		if a4<>a2 then
		if a4<>a1 then
		presist[a4]:=0;
		end;
		number2:=number2-1;
		if a3<>a2 then
		if a3<>a1 then
		presist[a3]:=0;	
		end;
	number2:=number2-1;
	if a2<>a1 then
	presist[a2]:=0;
	end;
	number2:=number2-1;
	presist[a1]:=0;
	end;
writeln('shortest way is');
for i:=1 to n do
write(short[i],'  ');
writeln;
end.