#include <iostream>
#include <cstdlib>
#include "location.h"
#include "apvector.h"

apvector<location> offset(8);

int withinBounds(location l, int m, int n){
	int i = l.getRow();
	int j = l.getCol();

	if ((i >= 0) && (i < m) && (j >= 0) && (j < n))
		return true;
	else
		return false;
}

int numberOfNeighbors(location l, int m, int n){
	int count = 0;

	for (int i = 0; i < 8; i++)
		if (withinBounds(l + offset[i], m, n))
			count++;

	return count;
}


location getNeighbor(location l, int t, int m, int n){
	int neighborCount = 0;
	for (int i = 0; i < 8; i++){
		location newLocation = l + offset[i];
		if (withinBounds(newLocation, m, n))
			neighborCount++;
		if(neighborCount == t)
			return newLocation;
	}

}

bool areNeighbors(location l1, location l2, int m, int n){
	int numNeighbors = numberOfNeighbors(l1, m, n);
	for(int i = 1; i <= numNeighbors; i++)
		if (l2 == getNeighbor(l1, i+1, m, n))
			return true;

	return false;
}

bool recursiveKnightsTour(location & currentSource,
			int & m, int & n,
			apvector< apvector<bool> > & visited,
			int & count,
			location & source,
			apvector<location> & tour){


	int currentRow = currentSource.getRow();
	int currentCol = currentSource.getCol();
	visited[currentRow][currentCol] = true;
	count++;

	tour.push_back(currentSource);

	// base case: are we successfully done?
	if((areNeighbors(currentSource, source, m, n)) && (count == m * n))
		return true;
	
	// get the number of neighbors of the current source
	int numNeighbors = numberOfNeighbors(currentSource, m, n);
	
	// scan the neighbors and visit the first neighbor not
	// yet visited
	bool done = false;
	for(int i = 1; i <= numNeighbors; i++){
		location neighbor = getNeighbor(currentSource, i, m, n);

		int r = neighbor.getRow();
		int c = neighbor.getCol();

		if(!visited[r][c])
			done = recursiveKnightsTour(neighbor, m, n, visited, count, source, tour);

		if (done)
			return true;	
	}

	visited[currentRow][currentCol] = false;
	tour.pop_back();
	count--;
	return false;
}	

apvector<location> knightsTour(int m, int n){

	offset[0].setRow(-1); offset[0].setCol(2);
	offset[1].setRow(-2); offset[1].setCol(+1);
	offset[2].setRow(-2); offset[2].setCol(-1);
	offset[3].setRow(-1); offset[3].setCol(-2);
	offset[4].setRow(+1); offset[4].setCol(-2);
	offset[5].setRow(+2); offset[5].setCol(-1);
	offset[6].setRow(+2); offset[6].setCol(+1);
	offset[7].setRow(+1); offset[7].setCol(+2);

	apvector< apvector<bool> > visited(m);

	// Resize and initialize visited
	for(int i = 0; i < m; i++)
		visited[i].resize(n);

	for(int i = 0; i < m; i++)
                for(int j = 0; j < n; j++)
                        visited[i][j] = false;


        // this is where the tour starts
	location source(1, 1);

        // this the the number of squares already visited
	int count  = 0;

        // the tour will be stored in this variable
	apvector<location> tour;

        // Call the recursive version of the knights tour function
	bool done = recursiveKnightsTour(source, m, n, visited, count, source, tour);

        return tour;
}


int main(){

int m, n;

//cout << "Input the number of rows followed by the number of columns:" << endl;
cin >> m;
cin >> n;

apvector<location> tour = knightsTour(m, n);

if(tour.size() > 0){
	for(int i = 0; i < tour.size(); i++)
		cout << tour[i].getRow() << " " << tour[i].getCol() << endl;
}
else
	cout << "No tour exists " << endl;

return EXIT_SUCCESS;
}