Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1659. Раскраска в три цвета
Олимпиадные задачи на русском языке| 04/07/2011 | Лето 2011 - дорешивание (15A) |
| 22/07/2011 | Лето 2011 - 15 (A) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Петя нарисовал на бумаге `n` кружков и соединил некоторые пары кружков линиями.
После этого он раскрасил каждый кружок в один из трех цветов — красный,
синий или зеленый.
Теперь Петя хочет изменить их раскраску. А именно — он хочет перекрасить
каждый кружок в некоторый другой цвет так, чтобы никакие два кружка одного
цвета не были соединены линией. При этом он хочет обязательно перекрасить
каждый кружок, а перекрашивать кружок в тот же цвет, в который он был раскрашен
исходно, не разрешается.
Помогите Пете решить, в какие цвета следует перекрасить кружки, чтобы выполнялось
указанное условие.
Ввод
Первая строка содержит два целых числа `n` и `m` — количество кружков и количество
линий, которые нарисовал Петя, соответственно (`1\ ≤\ n\ ≤\ 1000`, `0\ ≤\ m\ ≤\ 20\ 000`).
Следующая строка содержит `n` символов из множества {'R', 'G', 'B'}
— `i`-й из этих символов означает цвет, в который раскрашен `i`-й кружок
('R' — красный, 'G' — зеленый, 'B' — синий).
Следующие `m` строк содержат по два целых числа — пары кружков, соединенных
отрезками.
Вывод
Выведите в выходной файл одну строку, состоящую из `n` символов из множества
{'R', 'G', 'B'} — цвета кружков после перекраски.
Если решений несколько, выведите любое.
Если решения не существует, выведите в выходной файл слово "Impossible".
Пример ввода 1
4 5 RRRG 1 3 1 4 3 4 2 4 2 3
Пример вывода 1
BBGR
Пример ввода 2
4 5 RGRR 1 3 1 4 3 4 2 4 2 3
Пример вывода 2
Impossible
