Domino Tiling on a Partially Removed Grid

You are given a grid of size \(H \times W\) which consists of unit cells. Some cells are missing (removed) from the grid. The remaining cells are to be exactly covered by placing 1 \(\times\) 2 domino pieces. Each domino covers two adjacent cells and may be placed either horizontally or vertically (i.e. by rotating 90°).

A tiling is valid if and only if:

• Every remaining (non-missing) cell is covered by exactly one domino.
• No domino goes outside the grid boundaries or covers a missing cell.

Determine whether it is possible to tile the grid using the domino pieces.

Note: Domino pieces can be rotated by 90°.

In mathematical notation, let \(\mathcal{G}\) be a grid of size \(H \times W\) with exactly \(K\) cells removed. Let \(R\) be the set of remaining cells. The task is to decide if there exists a partition of \(R\) into pairs \((c_1, c_2)\) such that \(c_1\) and \(c_2\) are adjacent cells in \(\mathcal{G}\).

inputFormat

The first line contains three integers \(H\), \(W\) and \(K\) \( (1 \le H, W \le 50,\; 0 \le K < H \times W)\) representing the number of rows, columns, and the number of missing cells respectively.

Each of the following \(K\) lines contains two integers \(r\) and \(c\) (1-indexed) which indicate that the cell in row \(r\) and column \(c\) is missing.

outputFormat

If the grid can be exactly tiled by domino pieces, output Yes. Otherwise, output No.

sample

2 2 0

Yes