print1659. Раскраска в три цвета

printРаскраска в три цвета

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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
Источник: VI Всероссийская командная олимпиада школьников по программированию, 2005

loading