SGU 190 Dominoes 4/10

先看看這個題目：

試證明想要在一個N*N但是對角的兩格不見了的棋盤
用2*1的塊體完整覆蓋是不可能的。

像這樣
OOX
OOO
XOO

首先N是奇數很簡單，但N是偶數怎麼辦呢？
其實你知道一個2*1的塊體一定會覆蓋到黑色跟白色（想想棋盤）
而黑色跟白色數目不等，所以當然不可能囉！

====================================

根據上題的概念，就可以發現這題很簡單

但仍然是一題有趣的題目

很明顯就是要做配對，而且要是完全配對

因為他是二分圖，所以弄一弄就解決囉～

//By momo
#include
#include
#include
#include

#define N 45
#define PB push_back
#define SZ(x) (int)(x).size()
#define FOR(it, c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)

using namespace std;

vector<int> G[N*N], ans1, ans2;
int n, m, tbl[N][N], mch[N*N], vst[N*N];
void add_edge(int a, int b){ G[a].PB(b), G[b].PB(a); }

void Input(){
    scanf("%d%d", &n, &m);
    for(int i = 0, x, y; i < m; i++){
        scanf("%d%d", &x, &y);
        tbl[x-1][y-1] = 1;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0, x, y; j < n; j++){
            if(tbl[i][j]) continue;
            x = i+0, y = j+1;
            if(x < n && y < n && !tbl[x][y]) add_edge(i*n+j, x*n+y);
            x = i+1, y = j+0;
            if(x < n && y < n && !tbl[x][y]) add_edge(i*n+j, x*n+y);
        }
    }
}

bool Bi(int p){
    vst[p] = 1;
    FOR(it, G[p]){
        int w = mch[*it];
        if(w == -1 || !vst[w] && Bi(w)){
            mch[*it] = p;
            return 1;
        }
    }
    return 0;
}

void make(int i, int j){
    int x  = i/n, y  = i%n;
    int xx = j/n, yy = j%n;
    if(x+y > xx+yy) swap(x, xx), swap(y, yy);
    if(x < xx) ans1.PB(x*n+y);
    else ans2.PB(x*n+y);
}

void Solve(){
    int cnt = 0;
    memset(mch, -1, sizeof(mch));
    if((n*n - m) % 2){ puts("No"); return; }
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){
        if(tbl[i][j] || (i+j) % 2 == 0) continue;
        memset(vst, 0, sizeof(vst)); if(Bi(i*n+j)) cnt++;
    }
    if(cnt != (n*n - m) / 2){ puts("No"); return; }
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){
        if(tbl[i][j] || (i+j) % 2 == 1) continue;
        int x = mch[i*n+j]; make(i*n+j, x);
    }
    puts("Yes");
    printf("%d\n", SZ(ans1));
    for(int i = 0; i < SZ(ans1); i++)
        printf("%d %d\n", ans1[i]/n+1, ans1[i]%n+1);
    printf("%d\n", SZ(ans2));
    for(int i = 0; i < SZ(ans2); i++)
        printf("%d %d\n", ans2[i]/n+1, ans2[i]%n+1);
}

int main(){
    Input();
    Solve();
}