시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
Петя нарисовал на бумаге $n$ кружков и соединил некоторые пары кружков линиями. После этого он раскрасил каждый кружок в один из трех цветов --- красный, синий или зеленый.
Теперь Петя хочет изменить их раскраску. А именно --- он хочет перекрасить каждый кружок в некоторый другой цвет так, чтобы никакие два кружка одного цвета не были соединены линией. При этом он хочет обязательно перекрасить каждый кружок, а перекрашивать кружок в тот же цвет, в который он был раскрашен исходно, не разрешается.
Помогите Пете решить, в какие цвета следует перекрасить кружки, чтобы выполнялось указанное условие.
Первая строка содержит два целых числа $n$ и $m$ --- количество кружков и количество линий, которые нарисовал Петя, соответственно ($1 \le n \le 1\,000$, $0 \le m \le 20\,000$).
Следующая строка содержит $n$ символов из множества 'R
', 'G
', 'B
' --- $i$-й из этих символов означает цвет, в который раскрашен $i$-й кружок ('R
' --- красный, 'G
' --- зеленый, 'B
' --- синий).
Следующие $m$ строк содержат по два целых числа --- пары кружков, соединенных отрезками.
Выведите в выходной файл одну строку, состоящую из $n$ символов из множества 'R
', 'G
', 'B
' --- цвета кружков после перекраски. Если решений несколько, выведите любое.
Если решения не существует, выведите в выходной файл слово "Impossible
".
4 5 RRRG 1 3 1 4 3 4 2 4 2 3
BBGR
4 5 RGRR 1 3 1 4 3 4 2 4 2 3
Impossible