A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.
A minimum vertex cover is a vertex cover with minimal cardinality.
Consider a set of all minimum vertex covers of a given bipartite graph.
Your task is to divide all vertices of the graph into three sets.
A vertex is in set N (“Never”) if there is no minimum vertex cover containing this vertex.
A vertex is in set A (“Always”) if it is a part of every minimum vertex cover of the given graph.
If a vertex belongs neither to N nor to A, it goes to the set E (“Exists”).
Input
The first line of input contains three integers n, m, k: the size of the first vertex set of the bipartite graph, the size of the second vertex set and the number of edges (1 ≤ n, m ≤ 1000; 0 ≤ k ≤ 10^{6}).
Next k lines contain pairs of numbers of vertices, connected by an edge. First number denotes a vertex from the first set, second — from the second set.
Vertices in each set are numbered starting from one.
No pair of vertices is connected by more than one edge.
Output
On the first line, print a sequence of n letters ‘N’, ‘E’, ‘A’ without spaces. The letter on position i corresponds
to the set containing ith vertex of the first set. The second line must contain the answer for the second vertex set in the same format.
Sample
input  output 

11 9 22
1 1
1 2
1 3
1 8
1 9
2 1
2 3
3 2
3 4
4 3
4 5
5 2
5 4
5 6
6 6
6 7
7 5
7 7
8 7
9 7
10 7
11 7
 AEEEEEENNNN
EEEEEEANN

Problem Author: Alexey Danilyuk
Problem Source: Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014