题意：

n*n的矩形阵(n<=5)，由2*n*(n+1)根火柴构成，那么当中会有非常多诸如边长为1，为2...为n的正方形，如今能够拿走一些火柴，那么就会有一些正方形被破坏掉。

求在已经拿走一些火柴的情况下。还须要拿走至少多少根火柴能够把全部的正方形都破坏掉。

思路：

对于每一个位置遍历全部可能的边长，确定这个边长下的正方形的边相应的都是数字几，而且把正方形从1開始编号。

然后依据编号，把正方形和数字建边记录方便以下建图。

然后以火柴棍为行，正方形为列，建立dancing link

然后求解。

这里注意的是，须要强行插入某些行。

代码：

#include"stdio.h"

#include"algorithm"

#include"string.h"

#include"iostream"

#include"cmath"

#include"queue"

#include"map"

#include"vector"

#include"string"

using namespace std;

#define RN 70

#define CN 70

#define N 70*70

int fuck[123];

vector<int>edge[123];

struct DLX

{

    int n,m,C;

    int U[N],D[N],L[N],R[N],Row[N],Col[N];

    int H[RN],S[CN],cnt,ans[RN];

    void init(int _n,int _m)

    {

        n=_n;

        m=_m;

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

        {

            S[i]=0;

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

            L[i]=(i==0?m:i-1);

            R[i]=(i==m?

0:i+1);

        }

        C=m;

        for(int i=1; i<=n; i++) H[i]=-1;

    }

    void link(int x,int y)

    {

        C++;

        Row[C]=x;

        Col[C]=y;

        S[y]++;

        U[C]=U[y];

        D[C]=y;

        D[U[y]]=C;

        U[y]=C;

        if(H[x]==-1) H[x]=L[C]=R[C]=C;

        else

        {

            L[C]=L[H[x]];

            R[C]=H[x];

            R[L[H[x]]]=C;

            L[H[x]]=C;

        }

    }

    void del(int x)

    {

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

        {

            R[L[i]]=R[i];

            L[R[i]]=L[i];

        }

    }

    void rec(int x)

    {

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

        {

            R[L[i]]=i;

            L[R[i]]=i;

        }

    }

    int used[CN];

    int h()

    {

        int sum=0;

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

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

        {

            if(used[i]==0)

            {

                sum++;

                used[i]=1;

                for(int j=D[i]; j!=i; j=D[j]) for(int k=R[j]; k!=j; k=R[k]) used[Col[k]]=1;

            }

        }

        return sum;

    }

    void dance(int x)

    {

        if(x+h()>=cnt) return ;

        if(R[0]==0)

        {

            cnt=min(cnt,x);

            return ;

        }

        int now=R[0];

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

        {

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

                now=i;

        }

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

        {

            del(i);

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

            dance(x+1);

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

            rec(i);

        }

        return ;

    }

    void DeleteTrick(int r)  //强行先放入某行。

    {

        if(H[r] == -1) return ;

        for(int i = D[H[r]]; i != H[r]; i = D[i])

        {

            if(H[Row[i]] == i)

            {

                if(R[i] == i)

                {

                    H[Row[i]] = -1;

                }

                else

                {

                    H[Row[i]] = R[i];

                }

            }

            L[R[i]] = L[i];

            R[L[i]] = R[i];

        }

        for(int i = R[H[r]]; i != H[r]; i = R[i])

        {

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

            {

                if(H[Row[j]] == j)

                {

                    if(R[j] == j)

                    {

                        H[Row[j]] = -1;

                    }

                    else

                    {

                        H[Row[j]] = R[j];

                    }

                }

                L[R[j]] = L[j];

                R[L[j]] = R[j];

            }

        }

    }

} dlx;

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        int n,m;

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

        for(int i=0; i<m; i++) scanf("%d",&fuck[i]);

        for(int i=0; i<=70; i++) edge[i].clear();

        int sum=0;

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

        {

            for(int j=1; j<=n; j++)

            {

                int num=(i-1)*(n+n+1)+j;

                int lit=min(n-i+1,n-j+1);

                for(int k=1; k<=lit; k++)

                {

                    sum++;

                    int up,down,left,right;

                    up=num;

                    left=num+n;

                    right=left+k;

                    down=up+k*(n+n+1);

                    for(int o=0; o<k; o++)

                    {

                        edge[up+o].push_back(sum);

                        edge[left+o*(n+n+1)].push_back(sum);

                        edge[right+o*(n+n+1)].push_back(sum);

                        edge[down+o].push_back(sum);

                    }

                }

            }

        }

        dlx.init(2*n*(n+1),sum);

        for(int i=1; i<=2*n*(n+1); i++)

        {

            for(int j=0; j<(int)edge[i].size(); j++) dlx.link(i,edge[i][j]);

        }

        int fff[123];

        memset(fff,0,sizeof(fff));

        //for(int j=0; j<(int)edge[1].size(); j++) printf("%d ",edge[1][j]);

        //puts("");

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

        {

            dlx.DeleteTrick(fuck[i]);

        }

        dlx.cnt=999;

        dlx.dance(0);

        printf("%d\n",dlx.cnt);

    }

    return 0;

}

/*

4

4 10

1 2 3 4 5 6 7 8 9 10

*/