题意：一个 n x m 的矩形(1 <= n, m <= 30)，现给出这个矩形中 p 个（1 <= p <= 500）子矩形的左下角与右下角坐标，问最少用多少个子矩形能够恰好组成这个 n x m 的大矩形。

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3372

——>>这是精确覆盖问题，而DLX正是解决精确覆盖问题的有利武器。。

模型转换：将原矩形变成一行，作为 DLX 中的列，表示要被覆盖一次且仅一次的目标。子矩形则是行中的一些点，每一个子矩形作为 DLX 的一行，它所覆盖行中的点的位置标为1，其余位标为0，则问题转化为：选出最少的行，使得选出的行中每一列有且仅有一个1，这正是 DLX 解决的问题。。

注：在往下一层 dfs 的时候，假设检測返回值为真，可别来个return true，这时会中断后面的搜索（非常隐秘地 WA 了几发）。。为了方便，我不要返回值了。。

为了加快搜索，能够来个剪枝，dfs 时检測当前深度是否 >= 已搜索到的可满足要求的长度。。

#include <cstdio>

#include <cstring>

const int MAXN = 30 + 10;

const int MAXR = 500 + 10;

const int MAXC = 30 * 30 + 10;

const int MAXNODE = MAXR * MAXC;

const int INF = 0x3f3f3f3f;

struct DLX

{

    int sz;

    int H[MAXR], S[MAXC];

    int row[MAXNODE], col[MAXNODE];

    int U[MAXNODE], D[MAXNODE], L[MAXNODE], R[MAXNODE];

    int Min;

    void Init(int n)

    {

        for (int i = 0; i <= n; ++i)

        {

            U[i] = D[i] = i;

            L[i] = i - 1;

            R[i] = i + 1;

        }

        L[0] = n;

        R[n] = 0;

        sz = n + 1;

        memset(S, 0, sizeof(S));

        memset(H, -1, sizeof(H));

    }

    void Link(const int& r, const int& c)

    {

        row[sz] = r;

        col[sz] = c;

        D[sz] = D[c];

        U[D[c]] = sz;

        D[c] = sz;

        U[sz] = c;

        if (H[r] == -1)

        {

            H[r] = L[sz] = R[sz] = sz;

        }

        else

        {

            R[sz] = R[H[r]];

            L[R[H[r]]] = sz;

            R[H[r]] = sz;

            L[sz] = H[r];

        }

        S[c]++;

        sz++;

    }

    void Remove(const int& c)

    {

        L[R[c]] = L[c];

        R[L[c]] = R[c];

        for (int i = D[c]; i != c; i = D[i])

        {

            for (int j = R[i]; j != i; j = R[j])

            {

                U[D[j]] = U[j];

                D[U[j]] = D[j];

                S[col[j]]--;

            }

        }

    }

    void Restore(const int& c)

    {

        for (int i = U[c]; i != c; i = U[i])

        {

            for (int j = L[i]; j != i; j = L[j])

            {

                S[col[j]]++;

                U[D[j]] = j;

                D[U[j]] = j;

            }

        }

        L[R[c]] = c;

        R[L[c]] = c;

    }

    void Dfs(int cur)

    {

        if (cur >= Min) return;

        if (R[0] == 0)

        {

            if (cur < Min)

            {

                Min = cur;

            }

            return;

        }

        int c = R[0];

        for (int i = R[0]; i != 0; i = R[i])

        {

            if (S[i] < S[c])

            {

                c = i;

            }

        }

        Remove(c);

        for (int i = D[c]; i != c; i = D[i])

        {

            for (int j = R[i]; j != i; j = R[j])

            {

                Remove(col[j]);

            }

            Dfs(cur + 1);

            for (int j = L[i]; j != i; j = L[j])

            {

                Restore(col[j]);

            }

        }

        Restore(c);

    }

    void Solve()

    {

        Min = INF;

        Dfs(0);

        Min != INF ? printf("%d\n", Min) : puts("-1");

    }

} dlx;

int ReadInt()

{

    int ret = 0;

    char ch;

    while ((ch = getchar()) && ch >= '0' && ch <= '9')

    {

        ret = ret * 10 + ch - '0';

    }

    return ret;

}

void Read()

{

    int n, m, p;

    scanf("%d%d%d", &n, &m, &p);

    dlx.Init(n * m);

    getchar();

    for (int i = 1; i <= p; ++i)

    {

        int x1 = ReadInt();

        int y1 = ReadInt();

        int x2 = ReadInt();

        int y2 = ReadInt();

        for (int j = y1 + 1; j <= y2; ++j)

        {

            for (int k = x1 + 1; k <= x2; ++k)

            {

                dlx.Link(i, (j - 1) * n + k);

            }

        }

    }

}

int main()

{

    int T;

    scanf("%d", &T);

    while (T--)

    {

        Read();

        dlx.Solve();

    }

    return 0;

}