记录编号	124425	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	二分图游戏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.129 s
提交时间	2014-10-03 22:36:07	内存使用	0.33 MiB

/*
* this code is made by cstdio
* Problem: 1403
* Verdict: Accepted
* Submission Date: 2014-10-03 09:29:52
* Time: 820MS
* Memory: 2368KB
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
const int SIZEN=1010;
int N1,N2,N,M;
vector<int> c[SIZEN];
int match[SIZEN]={0};
bool vis[SIZEN]={0};
bool findpath(int x){
    if(vis[x]) return false;
    vis[x]=true;
    for(int i=0;i<c[x].size();i++){
        int u=c[x][i];
        if(!vis[u]){
            vis[u]=true;
            if(!match[u]||findpath(match[u])){
                match[u]=x;
                match[x]=u;
                return true;
            }
        }
    }
    return false;
}
bool mustcov[SIZEN]={0};
void work(void){
    memset(match,0,sizeof(match));
    memset(mustcov,0,sizeof(mustcov));
    for(int i=1;i<=N1;i++){
        memset(vis,0,sizeof(vis));
        findpath(i);
    }
    for(int i=1;i<=N;i++){
        if(!match[i]) continue;
        int m=match[i];
        match[m]=match[i]=0;
        memset(vis,0,sizeof(vis));
        vis[i]=true;
        if(!findpath(m)){
            mustcov[i]=true;
            match[m]=i;
            match[i]=m;
        }
    }
    for(int i=1;i<=N1;i++) printf(mustcov[i]?"N":"P");
    printf("\n");
    for(int i=N1+1;i<=N;i++) printf(mustcov[i]?"N":"P");
    printf("\n");
}
bool read(void){
    if(scanf("%d%d%d",&N1,&N2,&M)==EOF) return false;
    N=N1+N2;
    for(int i=1;i<=N;i++) c[i].clear();
    int a,b;
    for(int i=1;i<=M;i++){
        scanf("%d%d",&a,&b);
        c[a].push_back(N1+b);
        c[N1+b].push_back(a);
    }
    return true;
}
int main(){
    freopen("graphgame.in","r",stdin);
    freopen("graphgame.out","w",stdout);
    read();
    work();
    return 0;
}