|
Игра на графе
(Время: 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.TXT | OUTPUT.TXT |
|---|
| 1 | 3 3 5
1 1
1 2
1 3
2 1
3 1 | NPP
NPP |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
