题目链接:http://poj.org/problem?id=2446
Time Limit: 2000MS Memory Limit: 65536K

Description

Alice and Bob often play games on chessboard. One day, Alice draws a board with size M * N. She wants Bob to use a lot of cards with size 1 * 2 to cover the board. However, she thinks it too easy to bob, so she makes some holes on the board (as shown in the figure below). Description


We call a grid, which doesn’t contain a hole, a normal grid. Bob has to follow the rules below: 
1. Any normal grid should be covered with exactly one card. 
2. One card should cover exactly 2 normal adjacent grids. 

Some examples are given in the figures below: 

 A VALID solution.

An invalid solution, because the hole of red color is covered with a card.

 An invalid solution, because there exists a grid, which is not covered.

Your task is to help Bob to decide whether or not the chessboard can be covered according to the rules above.

Input

There are 3 integers in the first line: m, n, k (0 < m, n <= 32, 0 <= K < m * n), the number of rows, column and holes. In the next k lines, there is a pair of integers (x, y) in each line, which represents a hole in the y-th row, the x-th column.

Output

If the board can be covered, output "YES". Otherwise, output "NO".

Sample Input

4 3 2
2 1
3 3

Sample Output

YES

Hint

 
A possible solution for the sample input.

Problem solving report:

Description:给你一个棋盘，棋盘上有几个洞。要求你用一些1*2的卡片覆盖没有洞的区域，一个格子仅仅能有一张卡片覆盖，判断能否恰好覆盖。
Problem solving:两个相邻格子的坐标和必定奇偶性不同，可以利用这个奇偶性建图，然后跑一遍二分匹配就行了。

Accepted Code:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1030;
int n, m, cnt1, cnt2;
int match[MAXN], G[35][35];
int arr[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool vis[MAXN], mp[MAXN][MAXN];
bool DFS(int x) {
    for (int i = 1; i <= cnt2; i++) {
        if (!vis[i] && mp[x][i]) {
            vis[i] = true;
            if (!match[i] || DFS(match[i])) {
                match[i] = x;
                return true;
            }
        }
    }
    return false;
}
int count() {
    int ans = 0;
    memset(match, 0, sizeof(match));
    for (int i = 1; i <= cnt1; i++) {
        memset(vis, false, sizeof(vis));
        if (DFS(i))
            ans++;
    }
    return ans;
}
int main() {
    int a, b, k, ans;
    while (~scanf("%d%d%d", &n, &m, &k)) {
        memset(G, false, sizeof(G));
        memset(mp, false, sizeof(mp));
        for (int i = 0; i < k; i++) {
            scanf("%d%d", &a, &b);
            G[b][a] = -1;
        }
        cnt1 = cnt2 = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (~G[i][j]) {
                    if ((i + j) & 1)
                        G[i][j] = ++cnt1;
                    else G[i][j] = ++cnt2;
                }
            }
        }
        if (cnt1 != cnt2) {
            printf("NO\n");
            continue;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (~G[i][j] && ((i + j) & 1)) {
                    for (int k = 0; k < 4; k++) {
                        int x = i + arr[k][0];
                        int y = j + arr[k][1];
                        if (x >= 1 && x <= n && y >= 1 && y <= m && ~G[x][y])
                            mp[G[i][j]][G[x][y]] = true;
                    }
                }
            }
        }
        ans = count();
        if ((ans << 1) != n * m - k)
            printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}