#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <stack>

const int STACK = 1;
const int DISK  = 2;

struct Record {
  int what;
  int from;
  int to;
  int size;       // number of disks in stack  
  Record() {}     // needed for TSL template functions to work - sometimes they call
                  // the default constructor  
  Record(int x, int y, int z, int t) : what(x), from(y), to(z), size(t) {}
  int other()  { return 6 - from - to; }
  
}; 

// return the number of the 'other' pin


 main()
{
	
 int n = 5;	
	
 stack<Record, deque<Record, allocator<Record> >, allocator<Record> > s;	
 s.push( Record( STACK, 1, 3, 5) );
 
 while ( ! s.empty() ){
 	Record cur = s.top();
 	s.pop();
 	if ( cur.what == STACK ){  // it's a stack move
 		
 		if ( cur.size == 1 ) 
 		   s.push( Record( DISK, cur.from, cur.to, 1 ) );	   
	    else {
	       s.push( Record( STACK, cur.from, cur.other() , cur.size-1 ) );
	       s.push( Record( DISK, cur.from, cur.to, cur.size ) );
	       s.push( Record( STACK, cur.other(), cur.to , cur.size-1 ) );
	    }
	 }   
	 else{   // it's a single disk move
	    cout << "Move disk " << cur.size << " from " << cur.from << " to " << cur.to << endl;
	 }
 }
 cout << endl;
 cout << "The stack is empty. Done!";	        
}