题意：N与P在玩游戏，N有 n1 个点，P有 n2 个点，N的点与P的点之间有 m 条无向边。将一个石子放在其中一点，N先移动石子，沿边移动一次，石子移动前的点及与该点相连的边被删除，接着到P移动石子，谁不能移动谁就输。对每个初始位置输出胜负结果(1 ≤ n1; n2 ≤ 500, 0 ≤ m ≤ 50 000)。
题目链接：http://acdream.info/problem?pid=1403
——>>二分图的最大匹配可以有很多种，但是，其中可能有些点，无论是哪一种最大匹配方案，都是已盖点。。
那么，先手只要从这样的点沿着匹配边走，就可以把后手逼得走投无路。。（为什么呢？先手从 A 沿着匹配边走到 B，后者从 B 走到另一点 C，假设 C 不是已盖点，则最大匹配的一条匹配边 A - B 可改成 B - C，于是 A 不一定是已盖点，不满足我们的前提条件。。所以，C 一定是已盖点，于是先手可以继续沿着匹配边走，最后把对手干掉）于是，两边各两次dfs找出这样的点即可。。
#include <cstdio>
#include <cstring>const int MAXN = 1000 + 10;
const int MAXM = 50000 + 10;struct EDGE
{int to;int nxt;
} edge[MAXM << 1];int n1, n2, m;
int hed[MAXN], ecnt;
int S[MAXN], T[MAXN];
bool vis[MAXN];
bool maxMatch[MAXN];void Init()
{ecnt = 0;memset(hed, -1, sizeof(hed));
}void AddEdge(int u, int v)
{edge[ecnt].to = v;edge[ecnt].nxt = hed[u];hed[u] = ecnt++;
}void Read()
{int u, v;while (m--){scanf("%d%d", &u, &v);AddEdge(u, v + n1);AddEdge(v + n1, u);}memset(maxMatch, 0, sizeof(maxMatch));
}bool Match(int u)
{for (int e = hed[u]; e != -1; e = edge[e].nxt){int v = edge[e].to;if (!vis[v]){vis[v] = true;int temps = S[u];int tempt = T[v];S[u] = v;T[v] = u;if (tempt == -1 || Match(tempt)) return true;T[v] = tempt;S[u] = temps;}}return false;
}bool Judge(int u)
{vis[u] = true;if (S[u] == -1) return true;u = S[u];for (int e = hed[u]; e != -1; e = edge[e].nxt){int v = edge[e].to;if (!vis[v] && Judge(v)) return true;}return false;
}void GetMaxMatchPointLeft()
{memset(S, -1, sizeof(S));memset(T, -1, sizeof(T));for (int i = 1; i <= n1; ++i){memset(vis, 0, sizeof(vis));if (Match(i)){maxMatch[i] = true;}}for (int i = 1 + n1; i <= n2 + n1; ++i){if (T[i] != -1){memset(vis, 0, sizeof(vis));if (Judge(T[i])){maxMatch[T[i]] = false;}}}
}void GetMaxMatchPointRight()
{memset(S, -1, sizeof(S));memset(T, -1, sizeof(T));for (int i = 1 + n1; i <= n2 + n1; ++i){memset(vis, 0, sizeof(vis));if (Match(i)){maxMatch[i] = true;}}for (int i = 1; i <= n1; ++i){if (T[i] != -1){memset(vis, 0, sizeof(vis));if (Judge(T[i])){maxMatch[T[i]] = false;}}}
}void Output()
{for (int i = 1; i <= n1; ++i){maxMatch[i] ? putchar('N') : putchar('P');}puts("");for (int i = 1 + n1; i <= n2 + n1; ++i){maxMatch[i] ? putchar('N') : putchar('P');}puts("");
}int main()
{while (scanf("%d%d%d", &n1, &n2, &m) == 3){Init();Read();GetMaxMatchPointLeft();GetMaxMatchPointRight();Output();}return 0;
}