pc.cpp

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 19;

bool line_used[8][MAXN*3+3];

int idxs[MAXN][MAXN][8];

void init() {
    array<int, 2> ls[8] = {
        {1, 0},
        {0, 1},
        {1, 1},
        {1, -1},
        {2, 1},
        {1, 2},
        {2, -1},
        {-1, 2}
    };

    for (int i = 0; i < MAXN; ++i)
        for (int j = 0; j < MAXN; ++j)
            for (int d = 0; d < 8; ++d)
                idxs[i][j][d] = i * ls[d][0] + j * ls[d][1] + MAXN;
}

bool& used(int x, int y, int d) {
    return line_used[d][idxs[x][y][d]];
}

bool can_place(int x, int y) {
    for (int i = 0; i < 8; ++i) if (used(x, y, i)) return false;
    return true;
}

void flip(int x, int y) {
    for (int i = 0; i < 8; ++i) used(x, y, i) = not used(x, y, i);
}

int n;
int maxp, cntp;

void dfs(int i, int pc) {
    if (i == n) {
        if (pc > maxp) maxp = pc, cntp = 1;
        else if (pc == maxp) cntp += 1;
        return ;
    }

    if (n - i < maxp - pc) return ;

    for (int j = 0; j < n; ++j) {
        if (can_place(i, j)) {
            flip(i, j);
            dfs(i+1, pc+1);
            flip(i, j);
        }
    }

    dfs(i+1, pc);
}

void jizz() {
    scanf("%d", &n);

    memset(line_used, 0, sizeof line_used);

    int k; scanf("%d", &k);
    for (int i = 0; i < k; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        flip(x, y);
    }

    maxp = 0, cntp = 0;
    dfs(0, k);

    printf("%d %d\n", maxp, cntp);
}

int main() {
    init();

    int T; scanf("%d", &T); while (T--) jizz();
    return 0;
}

/*
$ g++ pc.cpp -std=c++11 -O2; time echo "1 19 0" | a; time echo "1 19 1 0 0" | a
19 307

real    0m3.799s
user    0m0.046s
sys     0m0.015s
19 18

real    0m0.269s
user    0m0.015s
sys     0m0.030s
*/