记录编号	182523	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	二分图游戏	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.612 s
提交时间	2015-08-28 14:11:34	内存使用	0.30 MiB

/*ABCDEFGHIJKLMNOPQRSTUVWXYZ
abcdefghijklmnopqrstuvwxyz*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;
typedef vector<int> vi;

const int MAX(1001);
int n1, n2, m, pre[MAX] = {0}, time_tip = 0, vis[MAX] = {0};
vi g[MAX];
bool find(int), ans[MAX] = {0};
ifstream fin("graphgame.in");
ofstream fout("graphgame.out");
#define cin fin
#define cout fout

main()
{
	ios::sync_with_stdio(false);
	cin >> n1 >> n2 >> m;
	for (int i = 0; i < m; ++i){
		int x, y;
		cin >> x >> y;
		g[x].push_back(n1 + y);
		g[n1 + y].push_back(x);
	}
	fin.close();
	
	for (int i = 1; i <= n1; ++i){
		time_tip++;
		find(i);
	}
	for (int i = 1; i <= n1 + n2; ++i){
		if (! pre[i])
			continue;
		m = pre[i];
		pre[i] = pre[m] = 0;
		vis[i] = ++time_tip;
		if (! find(m)){
			ans[i] = 1;
			pre[m] = i;
			pre[i] = m;
		}
	}
	
	for (int i = 1; i <= n1; ++i)
		if (ans[i])
			cout << 'N';
		else
			cout << 'P';
	cout << endl;
	for (int i = n1 + 1; i <= n1 + n2; ++i)
		if (ans[i])
			cout << 'N';
		else
			cout << 'P';
	fout.close(); 
//	cout << endl;	for (; ; );
}

bool find(int x)
{
	if (vis[x] == time_tip)
		return 0;
	vis[x] = time_tip;
	for (vi::iterator it = g[x].begin(); it != g[x].end(); ++it)
		if(vis[*it] != time_tip){
			if(! pre[*it] || find(pre[*it])){
				pre[*it] = x;
				pre[x] = *it;
				return true;
			}
		}
	return false;			
}