记录编号	264080	评测结果	AAAAAAAAAA
题目名称	[WC 2016] 挑战NPC	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.096 s
提交时间	2016-05-27 14:08:27	内存使用	0.35 MiB

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

const short maxl=9999;
int cas,n,m,e,num;
short match[1010],i,j;
vector <short> l[1010];
void add(short x,short y){
	l[x].push_back(y);
	l[y].push_back(x);
}
//[1..n]表示球,[n+1..n+m*3]表示筐,i筐分裂成[n+i*3-2,n+i*3] 

int z[2010],r,next[1010],fa[1010],mark[1010],vis[1010],t;
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void unit(int x,int y){
	x=find(x);y=find(y);
	if (x!=y) fa[x]=y;
}
int lca(int x,int y){
	t++;
	while (true){
		if (x!=-1){
			x=find(x);
			if (vis[x]==t) return x;
			vis[x]=t;
			if (match[x]!=-1) x=next[match[x]];
				else x=-1;
		}
		swap(x,y);
	}
}
void group(int a,int p){
	while (a!=p){
		int b=match[a],c=next[b];
		if (find(c)!=p) next[c]=b;
		if (mark[b]==2) mark[z[++r]=b]=1;
		if (mark[c]==2) mark[z[++r]=c]=1; 
		unit(a,b);unit(b,c);
		a=c;
	}
}
bool bfs(short x){
	for (short i=1;i<=num;i++)
		fa[i]=i,mark[i]=next[i]=-1,vis[i]=0;
	mark[z[r=1]=x]=1;
	for (short i=1;i<=r;i++){
		int x=z[i];
		for (short i=0;i<(int)l[x].size();i++){
			int y=l[x][i];
			if (match[x]==y) continue;
			if (mark[y]==2) continue;
			if (find(x)==find(y)) continue;
			if (match[y]==-1){
				next[y]=x;
				for (short i=y;i!=-1;){
					int u=next[i],v=match[u];
					match[i]=u;match[u]=i;
					i=v;
				}
				return 1;
			}
			if (mark[y]==1){
				int r=lca(x,y);
				if (find(x)!=r) next[x]=y;
				if (find(y)!=r) next[y]=x;
				group(x,r);
				group(y,r);
			}
			else{
				mark[z[++r]=match[y]]=1;
				mark[y]=2;
				next[y]=x;
			}
		}
	}
	return 0;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("npc.in","r",stdin);
	freopen("npc.out","w",stdout);
#endif
	scanf("%d",&cas);
	for (;cas>0;cas--){
		scanf("%d%d%d",&n,&m,&e);
		num=n+3*m;
		for (i=1;i<=num;i++) match[i]=-1;
		for (i=1;i<=num;i++) l[i].clear();
		int x,y,ans=0;
		for (i=1;i<=e;i++){
			scanf("%d%d",&x,&y);
			add(x,n+y*3);
			add(x,n+y*3-1);
			add(x,n+y*3-2);
		}
		for (i=1;i<=m;i++){
			add(n+i*3,n+i*3-1);
			add(n+i*3,n+i*3-2);
			add(n+i*3-1,n+i*3-2);
		}
		for (i=1;i<=n;i++)
		if (match[i]==-1) bfs(i);
		for (i=n+1;i<=num;i++)
		if (match[i]==-1) ans+=bfs(i);
		printf("%d\n",ans);
		for (i=1;i<=n;i++) printf("%d ",(match[i]+2-n)/3);
		putchar('\n');
	}
	return 0;
}