题意：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;

}