A - Graph Game
Time Limit: 6000/3000MS ( Java/Others) Memory Limit: 128000/64000KB (Java/Others) SubmitStatusProblem 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
Input
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
Output two lines. The first line must contain n1 characters, 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 n2 characters 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
NPP NPP
思路：二分图匹配，如果一个点可以不在最大匹配中，那么nick先走这个点一定输，否则一定赢