记录编号	181865	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	二分图游戏	最终得分	100
用户昵称	_stranger	是否通过	通过
代码语言	C++	运行时间	0.551 s
提交时间	2015-08-26 16:16:07	内存使用	0.34 MiB

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
inline int read(){
	int x;char ch;
	while(!isdigit(ch=getchar()));x=ch-48;
	while(isdigit(ch=getchar()))x=x*10+ch-48;
	return x;
}
vector<int> v[1001];
int match[1001],ans[1001],b[1001],tim;
int n1,n2,n,m;
bool find(int x){
	if(b[x]==tim)return 0;
	b[x]=tim;
	for(int i=0;i<v[x].size();i++){
		if(b[v[x][i]]!=tim){
			if(!match[v[x][i]]||find(match[v[x][i]])){
				match[v[x][i]]=x;
				match[x]=v[x][i];
				return 1;
			}
		}
	}
	return 0;
}
int main(){
   freopen("graphgame.in","r",stdin);freopen("graphgame.out","w",stdout);
	int x,y;
	n1=read();n2=read();m=read();
	n=n1+n2;
	for(int i=1;i<=m;i++){
		x=read();y=read();
		v[x].push_back(y+n1);
		v[y+n1].push_back(x);
	}
	for(int i=1;i<=n1;i++){
		tim++;
		find(i);
	}
	for(int i=1;i<=n;i++){
		if(!match[i]) continue;
		m=match[i];
		match[i]=match[m]=0;
		tim++;b[i]=tim;
		if(!find(m)){
			ans[i]=1;
			match[m]=i;
			match[i]=m;
		}
	}for(int i=1;i<=n1;i++)ans[i]?putchar('N'):putchar('P');
		putchar('\n');
		for(int i=n1+1;i<=n;i++)ans[i]?putchar('N'):putchar('P');
		putchar('\n');//while(1);
	return 0;
}