记录编号	181251	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1720.二分图游戏	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.827 s
提交时间	2015-08-23 17:53:29	内存使用	1.01 MiB

#define MAXN 1001UL
#define MAXE 100001UL

#include <cstdio>
#include <cstring>

struct Edge{
	int v,nx;
};

Edge edge[MAXE];

int ec,n,a,b,n1,n2,m,headlist[MAXN],link[MAXN];

bool used[MAXN];

inline void Match(int c,int d){
	link[c]=d;link[d]=c;
	return;
}

inline void Add_Edge(int u,int v){
	edge[++ec].v=v;
	edge[ec].nx=headlist[u];
	headlist[u]=ec;
	return;
}

bool dfs(int p){
	used[p]=1;
	for(int i=headlist[p];i;i=edge[i].nx){
		if(!used[edge[i].v]){
			used[edge[i].v]=1;
			if((!link[edge[i].v])||dfs(link[edge[i].v])){
				link[link[p]]=0;Match(p,edge[i].v);
				return true;
			}
		}
	}
	return false;
}

inline void Print(int p,int r){
	if(!r){
		putchar('N');
	}
	else{
		putchar('P');
	}
	if(p==n1){
		puts("");
	}
	return;
}

inline int in(){
	int x=0,c=getchar();
	while(c<'0'||c>'9'){
		c=getchar();
	}
	for(;c>='0'&&c<='9';c=getchar()){
		x=(x<<1)+(x<<3)+c-48;
	}
	return x;
}

int main(){
	freopen("graphgame.in","r",stdin);
	freopen("graphgame.out","w",stdout);	
	n1=in();n2=in();m=in();
	for(int i=1;i<=m;i++){
		a=in();b=in();
		Add_Edge(a,b+n1);Add_Edge(b+n1,a);
	}
	n=n1+n2;
	for(int i=1;i<=n1;i++){
		memset(used,0,sizeof(used));dfs(i);
	}
	for(int i=1;i<=n;i++){
		int stats=0;
		if(!link[i]){
			stats=1;
		}
		else{
			memset(used,0,sizeof(used));
			int bp=link[i];link[bp]=0;link[i]=0;used[i]=1;
			if(dfs(bp)){
				stats=1;
			}
			else{
				Match(i,bp);
			}
		}
		Print(i,stats);
	}
	return 0;
}