Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Игра на графе

(Время: 5 сек. Память: 16 Мб Сложность: 81%)

Наташа и Петя любят играть в следующую игру на лекциях по теории сложности. Они рисуют неориентированный двудольный граф G на листе бумаги и ставят фишку в одну из его вершин. После этого они делают ходы по очереди, Наташа ходит первой. Ход в игре заключается в том, что фишка перемещается по графу вдоль одного из ребер. После хода вершина, в которой фишка находилась перед ходом, а также все инцидентные ей ребра, удаляются из графа. Игрок, который не может сделать ход, проигрывает.

Вам задан граф, который нарисовали Наташа и Петя. Для каждой вершины графа определите, кто выиграет при оптимальной игре обоих игроков, если фишка будет исходно размещена в этой вершине.

Входные данные

Первая строка входного файла INPUT.TXT содержит три целых числа: n1, n2 и m – количество вершин в первой и второй доле, соответственно, а также количество ребер в графе (1 ≤ n1, n2 ≤ 500, 0 ≤ m ≤ 50 000). Следующие m строк описывают ребра – каждая строка содержит по два числа – номера вершин, соединенных соответствующим ребром. Вершины в каждой доле независимо пронумерованы, начиная с 1.

Выходные данные

В выходной файл OUTPUT.TXT выведите две строки. Первая строка должна содержать n1 символов, i-й символ должен быть 'N', если при исходном расположении фишки в i-й вершине первой доли, выигрывает Наташа и 'P', если выигрывает Петя. Вторая строка должна описывать вершины второй доли аналогичным образом.

Пример

INPUT.TXTOUTPUT.TXT
13 3 5
1 1
1 2
1 3
2 1
3 1
NPP
NPP

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru