意甲冠军：

它需要一个特殊的图，以找到最大匹配。该图的特征是：无向图，度的每个节点3。这是一个双边连接组件（the graph is 2-edge-connected (that is, at least 2 edges need to be removed in order to make the graph disconnected) 这一点是这样理解的把。。）

思路：

一般想法就直接建图求最大匹配，点的范围是5000，不优化可能超时，以下代码是890ms过的。

还有一种思路：

完备匹配的条件：

1. G是K（K>0）次正则二分图

2.G是无桥的三次正则图

3.G在去掉随意一个顶点子集S后，其子图中含顶点数为奇数的连通分支数不大于|S|

具有以上三个特征的图一定有完备匹配。且当中第三点是完备匹配的充要条件。

据此可得。题目中所给的图一定是完备匹配。答案是n/2。

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<vector>

#include<queue>

#include<map>

const int maxn=5010;

using namespace std;

int main()

{

    int n,a,b,t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(int i=0;i<3*n/2;i++)

            scanf("%d%d",&a,&b);

        printf("%d\n",n/2);

    }

    return 0;

}

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<vector>

#include<queue>

#include<map>

const int maxn=5010;

using namespace std;

int mx[maxn],my[maxn],n;

bool vis[maxn];

vector<int> e[maxn];

int path(int i)

{

    int j,sz=e[i].size();

    for(j=0;j<sz;j++)

    {

        int tmp=e[i][j];

        if(!vis[tmp])

        {

            vis[tmp]=1;

            if(my[tmp]==-1||path(my[tmp]))

            {

                my[tmp]=i;

                mx[i]=tmp;

                return 1;

            }

        }

    }

    return 0;

}

int hungary()

{

    int res=0;

    memset(mx,-1,(n+2)*sizeof(int));

    memset(my,-1,(n+2)*sizeof(int));

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

    {

        if(mx[i]==-1)

        {

            memset(vis,0,(n+2)*sizeof(vis[0]));

            res+=path(i);

        }

    }

    return res;

}

int main()

{

    int T,m,a,b,i;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        m=3*n/2;

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

            e[i].clear();

        while(m--)

        {

            scanf("%d%d",&a,&b);

            e[a].push_back(b);

            e[b].push_back(a);

        }

        printf("%d\n",hungary()/2);

    }

    return 0;

}