Description：

$n$ 个球和 $m$ 个筐，每个筐最多能装 $3$ 个球，每个球都必须放进一个筐中，求最多有几个筐子有不超过 $1$ 个球，以及最终每个球分别在哪个筐子中。

$1\leqslant n\leqslant 100$

Solution：

考虑为什么每个筐只能装 $3$ 个球，要求最多有几个筐有不超过 $1$ 个球，我们可以这样考虑，一个三个点的完全图(三角形)内部最多有一个匹配，而这样一个图最多向外连三个匹配，因此我们可以把每个筐拆三个点，内部连成完全图，然后球和对应的筐的三个点都连边，反正最后也只会连一个，然后求最大匹配，最大匹配 $-$ 球数就是筐内部连的个数，也就是只有不超过一个球的筐的个数。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res;

}

int n,m,p;

#define MAXM 110

#define MAXN 310

#define MAXE (MAXM * 3 + MAXN * MAXN * 3)

#define MAXP (MAXM * 3 + MAXN)

struct edge

{

	int to,nxt;

}e[MAXE << 1];

int edgenum = 0;

int lin[MAXP] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int f[MAXP],pre[MAXP],col[MAXP],match[MAXP];

int tag[MAXP],tim = 0;

int find(int x){return (f[x] == 0 ? x : f[x] = find(f[x]));}

int LCA(int u,int v)

{

	++tim;

	u = find(u);v = find(v);

	while(tag[u] != tim)

	{

		tag[u] = tim;

		u = find(pre[match[u]]);

		if(v)swap(u,v);

	}

	return u;

}

queue<int> q;

void blossom(int u,int v,int lca)

{

	while(find(u) != lca)

	{

		pre[u] = v;v = match[u];

		if(col[v] == 2)col[v] = 1,q.push(v);

		if(find(u) == u)f[u] = lca;

		if(find(v) == v)f[v] = lca;

		u = pre[v];

	}

	return;

}

int work(int s)

{

	memset(f,0,sizeof(f));

	memset(pre,0,sizeof(pre));

	memset(col,0,sizeof(col));

	while(!q.empty())q.pop();

	q.push(s);col[s] = 1;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			int v = e[i].to;

			if(find(k) == find(v))continue;

			if(col[v] == 2)continue;

			if(!col[v])

			{

				col[v] = 2;pre[v] = k;

				if(!match[v])

				{

					for(int i = v,pr;i;i = pr)

					{

						pr = match[pre[i]];

						match[i] = pre[i];match[pre[i]] = i;

					}

					return 1;

				}

				col[match[v]] = 1;

				q.push(match[v]);

			}

			else

			{

				int lca = LCA(k,v);

				blossom(k,v,lca);

				blossom(v,k,lca);

			}

		}

	}

	return 0;

}

void work()

{

	edgenum = 0;

	memset(lin,0,sizeof(lin));

	memset(match,0,sizeof(match));

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

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

	{

		add((i - 1) * 3 + 1 + n,(i - 1) * 3 + 2 + n);

		add((i - 1) * 3 + 2 + n,(i - 1) * 3 + 3 + n);

		add((i - 1) * 3 + 3 + n,(i - 1) * 3 + 1 + n);

	}

	int a,b;

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

	{

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

		add(a,(b - 1) * 3 + 1 + n);

		add(a,(b - 1) * 3 + 2 + n);

		add(a,(b - 1) * 3 + 3 + n);

	}

	int ans = 0;

	for(int i = 1;i <= n + 3 * m;++i)if(!match[i])ans += work(i);

	cout << ans - n << endl;

	for(int i = 1;i <= n;++i)printf("%d ",(match[i] - n - 1) / 3 + 1);

	return;

}

int main()

{

	int testcases = rd();

	while(testcases--)work();

	return 0;

}