ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2038. Minimum Vertex Cover

Time limit: 1.0 second
Memory limit: 64 MB
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 ≤ 106). 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 i-th vertex of the first set. The second line must contain the answer for the second vertex set in the same format.

Sample

inputoutput
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