Graph Game

Time Limit: 6000/3000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

      Nick and Peter like to play the following game when attending their complexity theory lectures. They draw an undirected bipartite graph G on a sheet of paper, and put a token to one of its vertices. After that they make moves in turn. Nick moves first.
      A move consists of moving the token along the graph edge. After it the vertex where the token was before the move, together with all edges incident to it, are removed from the graph. The player who has no valid moves loses the game.
      You are given the graph that Nick and Peter have drawn. For each vertex of the graph find out who wins if the token is initially placed in that vertex. Assume that both Nick and Peter play optimally


      The first line of the input file contains three integer numbers n1 , n2, and m — the number of vertices in each part, and the number of edges, respectively (1 ≤ n1; n2 ≤ 500, 0 ≤ m ≤ 50 000). The following m lines describe edges — each line contains the numbers of vertices connected by the corresponding edge. Vertices in each part are numbered independently, starting from 1.


      Output two lines. The first line must contain ncharacters, the i-th character must be ‘N’ in case Nick wins if the token is initially placed in the i-th vertex of the first part, and ‘P’ if Peter does. The second line must contain ncharacters and describe the second part in the same way.

Sample Input

3 3 5
1 1
1 2
1 3
2 1
3 1

Sample Output




Andrew Stankevich Contest 21


Solved Number48
Submit Number269
Problem Tags
graph matchings
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^