#C1072. Domino Tiling on a Rectangular Grid

    ID: 39956 Type: Default 1000ms 256MiB

Domino Tiling on a Rectangular Grid

Domino Tiling on a Rectangular Grid

You are given a rectangular grid with dimensions \(n\) rows and \(m\) columns. The task is to determine whether it is possible to completely tile the grid using domino tiles of size \(2\times1\) and \(1\times2\). A domino tile covers exactly two adjacent cells. Note that you cannot rotate or break the domino tiles, and they must not overlap or extend beyond the grid.

For a grid to be completely tiled by dominoes, the total number of cells \(n \times m\) must be even, because each domino covers exactly 2 cells. Therefore, if \(n \times m\) is even, the answer is "YES", otherwise, it is "NO".

Examples:

  • For a \(2\times2\) grid, the area is 4 (even), so the answer is "YES".
  • For a \(3\times3\) grid, the area is 9 (odd), so the answer is "NO".

inputFormat

The first line of the input contains a single integer \(t\) (the number of test cases). Each of the following \(t\) lines contains two space-separated integers \(n\) and \(m\) representing the number of rows and columns of the grid, respectively.

Input Format:

t
n m
n m
... (t test cases)

outputFormat

For each test case, print a single line containing "YES" if the grid can be completely tiled by the domino tiles, or "NO" otherwise.

Output Format:

YES/NO
YES/NO
... (t lines)
## sample
3
2 2
3 3
4 5
YES

NO YES

</p>