ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

C. Минимальное вершинное покрытие

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

Исходные данные

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

Результат

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

Пример

исходные данныерезультат
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
Автор задачи: Алексей Данилюк
Источник задачи: Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2038. Минимальное вершинное покрытие