class Brett
{
private boolean feld [] [];

Brett(int n)
	{feld = new boolean [n+1] [n+1];
	for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) feld [i] [j] =true;
	feld [1] [1] =false;
	feld [0] [0] =false;}

public boolean freiesFeld (Platz p)
	{return feld [p.getWag()] [p.getSen()];}

public void besetzeFeld (Platz p)
	{feld [p.getWag()] [p.getSen()]=false;}

public void befreieFeld (Platz p)
	{feld [p.getWag()] [p.getSen()]=true;}
}

class Platz
{
private int wag, sen;

Platz () {wag=sen=0;}
Platz (int w, int s) {wag=w;sen=s;}

public int getWag() {return wag;}

public int getSen() {return sen;}

public String toString() {return "["+wag+"/"+sen+"]";}

public void forbid() {wag=sen=0;}

public Platz [] moeglichkeiten (int n)
	{Platz moeg[] = new Platz [8];
	Platz p=this;
	moeg[0]=new Platz(p.getWag()+1,p.getSen()+2);
	moeg[1]=new Platz(p.getWag()+2,p.getSen()+1);
	moeg[2]=new Platz(p.getWag()+2,p.getSen()-1);
	moeg[3]=new Platz(p.getWag()+1,p.getSen()-2);
	moeg[4]=new Platz(p.getWag()-1,p.getSen()-2);
	moeg[5]=new Platz(p.getWag()-2,p.getSen()-1);
	moeg[6]=new Platz(p.getWag()-2,p.getSen()+1);
	moeg[7]=new Platz(p.getWag()-1,p.getSen()+2);
	for (int i=0;i<8;i++)
	   if (moeg[i].getWag()<1 || moeg[i].getWag()>n || moeg[i].getSen()<1 || moeg[i].getSen()>n) moeg[i].forbid();
	return moeg;}
}

class Springer
{
private static Brett schach;
private static Platz zuege[];
private static int loesungen=0;
private static int zyklen=0;
	
public static void main (String args[])
	{int n= Integer.parseInt(args[0]);
	schach=new Brett (n);
	zuege=new Platz [n*n];
	zuege[0]=new Platz(1,1);
	loese(0,n);
	System.out.println("That's all folks! Es waren "+loesungen+" Loesungen;");
	System.out.println("Davon waren "+zyklen+" Hamilton-Zyklen.");}

public static void loese (int counter,int n)
	{if (counter==n*n-1) gefunden(n);
	  else
	    {Platz m[]=new Platz[8];
	    m=zuege[counter].moeglichkeiten(n);
	    for (int i=0;i<8;i++)
	       if (schach.freiesFeld(m[i])) 
		  {zuege[counter+1]=m[i];
		  schach.besetzeFeld(zuege[counter]);
		  loese(counter+1,n);}
       	    schach.befreieFeld(zuege[counter]);}
	}

public static void gefunden(int n)
	{loesungen++;
	if (loesungen==1) ausdruck(n);
	if ((zuege[n*n-1].getWag()==3 && zuege[n*n-1].getSen()==2) || (zuege[n*n-1].getWag()==2 && zuege[n*n-1].getSen()==3))
		{zyklen++;
		if (zyklen==1) {System.out.println("Ein Hamilton-Zyklus:");ausdruck(n);}
		}
	}

public static void ausdruck(int n)
	{System.out.print(zuege[0].toString());
	for (int i=1;i<n*n;i++) System.out.print("->"+zuege[i].toString());
	System.out.println();
	System.out.println();}
}