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 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.
3 3 5
Andrew Stankevich Contest 21
No tag edit access