This problem is solvable for all cases except 4 × 4.

The important thing in the problem is to notice that there exists a structure that allows us to visit every cell of a 3 × 4 (or 4 × 3) rectangle and finish in a cell that is opposite to the starting cell. This can be seen in the following image, which is a solution for the 4 × 6 case:

And as can be seen in a solution of a 6 × 6 grid, this structure can be made higher:

And they can be put next to each other:

So now we can solve cases where n ≡ 2 (mod 4) or m ≡ 2 (mod 4). We still need a solution for the case n ≡ 0 (mod 4) or m ≡ 0 (mod 4). This can be solved by using the same structure as before, but this time making it wider and reducing this back to m ≡ 2 (mod 4) case:

And now we can combine all this into a 100p solution.

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
vector<string> res;
 
void addMoves(char c) {
	string add[4] = {"?00 -> 0?0", "?01 -> 0?1", "?10 -> 1?0", "?11 -> 1?1"};
	for (int i = 0; i < 4; ++i) {
		add[i][0] = c;
		add[i][8] = c;
		res.push_back(add[i]);
	}
}
void addSwaps(char a, char b) {
	string add[2] = {"?0_ -> _0?", "?1_ -> _1?"};
	for (int i = 0; i < 2; ++i) {
		add[i][0] = a;
		add[i][2] = b;
		add[i][7] = b;
		add[i][9] = a;
		res.push_back(add[i]);
	}
}
void addEat(char a, char zt, char ot) {
	string add = "?0 -> _";
 
	add[0] = a;
	add[6] = zt;
	res.push_back(add);
 
	add[1] = '1';
	add[6] = ot;
	res.push_back(add);
}
 
int main() {
	int k;
	cin >> k;
 
	// 2 commands to move start marker to start
	res.push_back("0X -> X0");
	res.push_back("1X -> X1");
 
	// 16 move commands
	addMoves('A');
	addMoves('B');
	addMoves('C');
	addMoves('D');
 
	// 12 swap commands
	addSwaps('B', 'A');
	addSwaps('C', 'B');
	addSwaps('C', 'A');
	addSwaps('D', 'C');
	addSwaps('D', 'B');
	addSwaps('D', 'A');
 
	// 2 commands for building space
	if (k == 2) {
		res.push_back("X0 -> EXA");
		res.push_back("X1 -> FXA");
	} else if (k == 3) {
		res.push_back("X0 -> EXAB");
		res.push_back("X1 -> FXAB");
	} else if (k == 4) {
		res.push_back("X0 -> EXABC");
		res.push_back("X1 -> FXABC");
	} else if (k == 5) {
		res.push_back("X0 -> EXABCD");
		res.push_back("X1 -> FXABCD");
	}
 
	// 8 commands for eating nums
	addEat('A', 'G', 'H');
	addEat('B', 'E', 'F');
	addEat('C', 'G', 'H');
	addEat('D', 'E', 'F');
 
	// 2 commands to move start marker to start
	res.push_back("EX -> XE");
	res.push_back("FX -> XF");
 
	// 4 commands to move end marker to end
	res.push_back("YE -> EY");
	res.push_back("YF -> FY");
	res.push_back("YG -> GY");
	res.push_back("YH -> HY");
 
	// 8 commands for flipping
	res.push_back("EI -> IE");
	res.push_back("FI -> IF");
	res.push_back("EJ -> JE");
	res.push_back("FJ -> JF");
	res.push_back("GK -> KG");
	res.push_back("HK -> KH");
	res.push_back("GL -> LG");
	res.push_back("HL -> LH");
 
	// 4 commands for turning
	res.push_back("GI -> K");
	res.push_back("HJ -> L");
	res.push_back("EK -> I");
	res.push_back("FL -> J");
 
	// 4 commands to make end start chains
	res.push_back("EY -> IY");
	res.push_back("FY -> JY");
	res.push_back("GY -> KY");
	res.push_back("HY -> LY");
 
	// 4 commands to make start eat
	res.push_back("XI -> X");
	res.push_back("XJ -> X");
	res.push_back("XK -> X");
	res.push_back("XL -> X");
 
	// 2 commands to make start
	res.push_back("0 -> X0");
	res.push_back("1 -> X1");
 
	// 4 commands to make end
	res.push_back("E -> EY");
	res.push_back("F -> FY");
	res.push_back("G -> GY");
	res.push_back("H -> HY");
 
	// 1 command to have start eat end
	res.push_back("XY -> _");
 
	// Print res
	cout << res.size() << '\n';
	for (auto str : res) cout << str << '\n';
}