Минимальное вершинное покрытие данного графа — это минимальное (по мощности) подмножество его вершин такое, что каждое ребро графа инцидентно хотя бы одной вершине.

Рассмотрим множество всех минимальных вершинных покрытий заданного двудольного графа. Ваша задача — разбить все вершины графа на три множества. Вершина входит в множество N («Never»), если не существует минимального вершинного покрытия, содержащего эту вершину. Вершина входит в множество A («All»), если она содержится во всех минимальных вершинных покрытиях. Если вершина не входит в множества N и A, то она входит в множество E («Exists»).

В первой строке входа располагаются три целых числа n, m и k — размер первой доли, размер второй доли и количество рёбер (1 ≤ n, m ≤ 1000; 0 ≤ k ≤ 10⁶). Далее в k строках располагаются пары чисел — номера вершин, соединённых рёбрами (первое число — номер вершины из первой доли, второе  — номер вершины из второй доли, вершины в долях нумеруются с единицы). Каждая пара вершин соединена не более чем одним ребром.

В первой строке требуется выдать последовательность из n букв «N», «E», «A» без пробелов, i-й символ которой обозначает множество, которому принадлежит i-я вершина первой доли. Во второй строке требуется выдать аналогичную последовательность для вершин второй доли.