ADA School (Editorial)

Let's consider the case where one of the grid dimensions is even. For example, let $n$ (the number of rows) be even. In this case, the rearrangement of students can be performed as follows:

If $n$ and $m$ are both odd, the rearrangement is impossible.

Consider a grid colored in a checkerboard pattern, where some cells are white and others are black. When a desk is moved, it must switch from a black cell to a white one, and vice versa. For the rearrangement to be possible, the number of white and black cells must be equal. Therefore, the total number of desks must be even.

However, when both $n$ and $m$ are odd, the total number of desks, n \times m, is an odd number, making the rearrangement impossible.

Algorithm implementation

Read the number of test cases $t$.

scanf("%d", &t);
while (t--)
{

Read the input data for each test case.

  scanf("%d %d", &n, &m);

If $n$ and $m$ are both odd, print "NO".

  if (n % 2 == 1 && m % 2 == 1)
    puts("NO");

Otherwise, print "YES". '

  else
    puts("YES");
}