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

#### Input

The first line of the input file contains three integer numbers n_{1} , n_{2}, and m — the number of vertices in each part, and the number of edges, respectively (1 ≤ n_{1}; n_{2} ≤ 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 n_{1 }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 n_{2 }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

#### Hint

#### Source

Andrew Stankevich Contest 21

#### Manager