这道题主要就是讲我们从任意点出发，每次走的都是没走过并且，曼哈顿距离大于1小于3的点，然后问能不能覆盖完整幅图。
这里就想到一个很经典的问题，（4399小游戏除草游戏？？？）以前玩过的一个小游戏倒是让我对这道题的解法有了方向的感觉，感觉每个点都有自己的稳定下一个点，固定方向（虽然答案不唯一）。
我们先把最上面一行走完，然后按照蛇（S）形走位……就可以了。但是我们这道题中是有限制的，我们不能一个一个点的走，不妨我们根据点的奇偶性，假设第一个点是（1，1）那么就是白色偶数点，假设（3，2）这个点就是黑色奇数点，这类意思。然后白子按照刚才的走法，黑子考虑最后两排是要交替着走还是继续按照刚才的规矩S形走。
代码量比较的长，但是附上了对应的注释……QAQ
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define efs 1e-6
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define max3(a, b, c) max(a, max(b, c))
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
int N, M;
inline bool In_map(int x, int y) { return x > 0 && y > 0 && x <= N && y <= M; }
pair<int, int> nex[105][105];
bool vis[105][105];
struct node
{
int x, y;
node(int a=0, int b=0):x(a), y(b) {}
};
int top, Stop;
node Que[105 * 105], Stap[105 * 105];
inline void init()
{
top = Stop = 0;
for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) vis[i][j] = false;
for(int i=1; i<=N; i++) nex[i][1] = nex[i][2] = MP(0, 0); //初始化
int i = 1;
//先白
for(i = 1; i + 2 <= M; i += 2) nex[1][i] = MP(1, i + 2);
if(N == 2)
{
int st = 0;
if(M & 1) { nex[1][M] = MP(2, M - 1); st = M - 1; }
else { nex[1][M - 1] = MP(2, M); st = M; }
for(; st - 2 >= 1; st -= 2) nex[2][st] = MP(2, st - 2);
//nex[2][st] = MP(1, 1); //白就不需要回归到原点构成环的操作了
}
else // N≥3
{
int beg;
if(M & 1) //第一排最后一个是白
{
nex[1][M] = MP(3, M);
for(int j = M; j >= 1; j--) //白子可以顺走，黑子最后的两排需要判断
{
if( (M - j) & 1 )
{
beg = N & 1 ? N - 1 : N;
for( ; beg - 2 >= 2; beg -= 2)
{
nex[beg][j] = MP(beg - 2, j);
}
nex[2][j] = MP(3, j - 1);
}
else
{
beg = 3;
for( ; beg + 2 <= N; beg += 2)
{
nex[beg][j] = MP(beg + 2, j);
}
if(N & 1) nex[beg][j] = MP(beg - 1, j - 1);
else nex[beg][j] = MP(beg + 1, j - 1);
}
}
}
else //第一排最后一个是黑
{
nex[1][M - 1] = MP(2, M);
for(int j = M; j >= 1; j--) //白子可以顺走，黑子最后的两排需要判断
{
if( (M - j) & 1 )
{
beg = N & 1 ? N : N - 1;
for( ; beg - 2 >= 2; beg -= 2)
{
nex[beg][j] = MP(beg - 2, j);
}
nex[beg][j] = MP(beg - 1, j - 1);
}
else
{
beg = 2;
for( ; beg + 2 <= N; beg += 2)
{
nex[beg][j] = MP(beg + 2, j);
}
if(N & 1) nex[beg][j] = MP(beg + 1, j - 1);
else nex[beg][j] = MP(beg - 1, j - 1);
}
}
}
}
//后黑
for(i = 2; i + 2 <= M; i += 2) nex[1][i] = MP(1, i + 2);
if(N == 2)
{
int st = 0;
if(M & 1) { nex[1][M - 1] = MP(2, M); st = M; } //第一排最后一个是白
else { nex[1][M] = MP(2, M - 1); st = M - 1; } //同时找到st的开始点，此时的黑，需要去构成环
for(; st - 2 >= 1; st -= 2) nex[2][st] = MP(2, st - 2);
nex[2][st] = MP(1, 2);
}
else //现在是 N ≥ 3
{
int beg;
if(M & 1) //第一排最后一个是白，并且如果M是奇数，意味着 M ≥ 3
{
nex[1][M - 1] = MP(2, M);
for(int j = M; j >= 3; j --)
{
if( (M - j) & 1 )
{
beg = N & 1 ? N : N - 1;
for(; beg - 2 >= 2; beg -= 2)
{
nex[beg][j] = MP(beg - 2, j);
}
nex[3][j] = MP(2, j - 1);
}
else
{
beg = 2;
for(; beg + 2 <= N; beg += 2)
{
nex[beg][j] = MP(beg + 2, j);
}
if(N & 1) nex[beg][j] = MP(N, j - 1);
else nex[beg][j] = MP(N - 1, j - 1);
}
}
if(N & 1)
{
for(int k = N; k >= 3; k--)
{
if(k & 1) nex[k][2] = MP(k - 1, 1);
else nex[k][1] = MP(k - 1, 2);
}
nex[2][1] = MP(1, 2);
}
else
{
nex[N - 1][2] = MP(N, 1);
nex[N][1] = MP(N - 2, 1);
for(int k = N - 2; k >= 3; k--)
{
if(k & 1) nex[k][2] = MP(k - 1, 1);
else nex[k][1] = MP(k - 1, 2);
}
nex[2][1] = MP(1, 2);
}
}
else //第一排最后一个是黑
{
nex[1][M] = MP(3, M);
for(int j = M; j >= 1; j--)
{
if( (M - j) & 1 )
{
beg = N & 1 ? N - 1 : N;
for(; beg + 2 >= 2; beg -= 2)
{
nex[beg][j] = MP(beg - 2, j);
}
nex[2][j] = MP(3, j - 1);
}
else
{
beg = 3;
for(; beg + 2 <= N; beg += 2)
{
nex[beg][j] = MP(beg + 2, j);
}
if(N & 1) nex[beg][j] = MP(beg - 1, j - 1);
else nex[beg][j] = MP(beg + 1, j - 1);
}
}
nex[2][1] = MP(1, 2);
}
}
}
int main()
{
int Cas; scanf("%d", &Cas);
while(Cas--)
{
scanf("%d%d", &N, &M);
init();
if(N == 1 && M == 1)
{
printf("YES\n");
printf("1 1\n");
continue;
}
if(N == 1 || M == 1)
{
printf("NO\n");
continue;
}
if(N == 2 && M == 2)
{
printf("NO\n");
continue;
}
init();
printf("YES\n");
if(In_map(3, 2))
{
int x = 1, y = 1, tx, ty;
Que[++top] = node(x, y);
while(nex[x][y].first && nex[x][y].second)
{
tx = nex[x][y].first; ty = nex[x][y].second;
Que[++top] = node(tx, ty);
x = tx; y = ty;
}
x = 3; y = 2;
vis[x][y] = true;
Stap[++Stop] = node(x, y);
while(!vis[nex[x][y].first][nex[x][y].second])
{
tx = nex[x][y].first; ty = nex[x][y].second;
vis[tx][ty] = true;
Stap[++Stop] = node(tx, ty);
x = tx; y = ty;
}
for(int i=Stop; i>=1; i--) printf("%d %d\n", Stap[i].x, Stap[i].y);
for(int i=1; i<=top; i++) printf("%d %d\n", Que[i].x, Que[i].y);
}
else if(In_map(2, 3))
{
int x = 1, y = 1, tx, ty;
Que[++top] = node(x, y);
while(nex[x][y].first && nex[x][y].second)
{
tx = nex[x][y].first; ty = nex[x][y].second;
Que[++top] = node(tx, ty);
x = tx; y = ty;
}
x = 2; y = 3;
vis[x][y] = true;
Stap[++Stop] = node(x, y);
while(!vis[nex[x][y].first][nex[x][y].second])
{
tx = nex[x][y].first; ty = nex[x][y].second;
vis[tx][ty] = true;
Stap[++Stop] = node(tx, ty);
x = tx; y = ty;
}
for(int i=Stop; i>=1; i--) printf("%d %d\n", Stap[i].x, Stap[i].y);
for(int i=1; i<=top; i++) printf("%d %d\n", Que[i].x, Que[i].y);
}
}
return 0;
}
